Online Course Discussion Forum

AIME sprint camp week 2

 
 
SunEthan的头像
AIME sprint camp week 2
SunEthan - 2023年12月11日 Monday 18:26
 

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!

 
LensmireJohn的头像
Re: AIME sprint camp week 2
LensmireJohn - 2023年12月12日 Tuesday 09:09
 

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!

SunEthan的头像
Re: AIME sprint camp week 2
SunEthan - 2023年12月12日 Tuesday 19:17
 

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