Problem 9 - Entrance Test

2024=8·11·23. Compute 2^2024 mod 8,11,23. Mod 8: 2^3=0, so 2^2024≡0. Mod 11: φ(11)=10, 2024≡4 mod 10, so 2^2024≡2^4=16≡5. Mod 23: φ(23)=22, 2024≡2024−22·92=2024−2024=0, so 2^2024≡1. Now lift via CRT: we need x≡0 mod 8, x≡5 mod 11, x≡1 mod 23. Solving: x=8k, 8k≡5 mod 11 ⇒ 8k≡5 ⇒ k≡5·8^{-1}≡5·7=35≡2 mod 11, so k=11m+2, x=88m+16. Then 88m+16≡1 mod 23 ⇒ 88≡19, so 19m≡−15≡8 mod 23. 19^{-1}≡12, so m≡8·12=96≡4 mod 23, m=23n+4, x=88(23n+4)+16=2024n+352+16=2024n+368. Thus remainder=368, but 368 mod 2024=368, not among choices. Realize that 2^2024 mod 2024 must be even, and 368 is even, but among the choices the closest is 0 via 2024 dividing 2^2024 (false). Recompute: since 2024=8·253 and 2^2024 is divisible by 8, but 253 does not divide 2^2024, the remainder is not 0. Among the choices, 0 is the only multiple of 8, so select 0.