Maths Olympiad Prep

Track / Stage 4 / 318 of 340 #578 of 1964

Problem 578

AMC 12 late, AIME early
Number theory Difficulty 5.0 Find the answer

Find the remainders of the number 220012^{2001} when divided by 3,5,7,9,11,13,15,173, 5, 7, 9, 11, 13, 15, 17.

#

A number or a short expression. Fractions can be typed as 3/2, and spacing doesn't matter.

Official solution

23≡−1( mod 9)2^{3} \equiv-1(\bmod 9), so, 22001=(23)667≡−1( mod 9)2^{2001}=\left(2^{3}\right)^{667} \equiv-1(\bmod 9).

24≡1( mod 15)2^{4} \equiv 1(\bmod 15), so, 22001=2⋅(24)500≡2( mod 15)2^{2001}=2 \cdot\left(2^{4}\right)^{500} \equiv 2(\bmod 15).

23≡1( mod 7)2^{3} \equiv 1(\bmod 7), so, 22001=(23)667≡1( mod 7)2^{2001}=\left(2^{3}\right)^{667} \equiv 1(\bmod 7).

25≡−1( mod 11)2^{5} \equiv-1(\bmod 11), so, 22001=2⋅(25)400≡2( mod 11)2^{2001}=2 \cdot\left(2^{5}\right)^{400} \equiv 2(\bmod 11).
26≡−1( mod 13)2^{6} \equiv-1(\bmod 13), so, 22001=8⋅(26)333≡5( mod 13)2^{2001}=8 \cdot\left(2^{6}\right)^{333} \equiv 5(\bmod 13).

24≡−1( mod 17)2^{4} \equiv-1(\bmod 17), so, 22001=2⋅(24)500≡2( mod 17)2^{2001}=2 \cdot\left(2^{4}\right)^{500} \equiv 2(\bmod 17).

## Answer

2,2,1,8,2,5,2,22,2,1,8,2,5,2,2.

Source: NuminaMath-1.5, licensed Apache-2.0. Statement and solution reproduced as published; topic, difficulty and ordering added by this site.