Online Course Discussion Forum

AIME sprint camp week 2

 
 
Picture of Ethan Sun
AIME sprint camp week 2
by Ethan Sun - Monday, December 11, 2023, 6:26 PM
 

Hello, I'm having trouble on problems 2 and 6, help would be appreciated.

Currently I have tried for number 2 for something like FLT, but didn't work.

For number 6 I noticed that 2303 is 47*49, and tried using mod 47 and mod 49 to try to use CRT, but it isn't going well.

Thanks!

 
Picture of John Lensmire
Re: AIME sprint camp week 2
by John Lensmire - Tuesday, December 12, 2023, 9:09 AM
 

Here's some hints:

For both questions the Chinese Remainder Theorem is helpful (2019 = 3*673 and 2303 = 47*49 as you noticed).

For 2) 673 is prime so that means we can apply Fermat's Little Theorem (FLT), which helps.

For 6) we can use FLT for (mod 47). For (mod 49) remember we can use the Euler's Totient Function and the extension to FLT. Since phi(49) = 49*(6/7) = 42, remember we know that if gcd(a, 49) = 1 then $a^{\phi(49)} = a^42 \equiv 1 \pmod{49}$.

Note it is not as efficient, but it is also possible to do more direct calculations since the power isn't too large. For example, since $47\equiv -2 \pmod{49}$, we know that$$47^8 \equiv (-2)^8 \equiv 256 \equiv  11 \pmod{49}.$$ Then, for example,$$47^{43} = (47^8)^5 \cdot 47^3 \equiv 11^5\cdot (-2)^3 \pmod{49}$$and you can continue from there.

Hope these hints help!

Picture of Ethan Sun
Re: AIME sprint camp week 2
by Ethan Sun - Tuesday, December 12, 2023, 7:17 PM
 

Thank you very much! I was able to solve the problems after this hint! This was very helpful