# Finding the remainder of a linear congruence

Okay so say I have $314^{420} \equiv r \pmod{1001}$ and I have to find what the remainder is, $r$ in this case. I know you could compute it by $gcd(314^{420}, 1001)$ and using EEA. But the numbers are too large for this case.

I also know that 1001 is a product of 3 prime numbers which was a hint that was pointed out to me. So $1001 = 7 * 11 * 13$. But I'm not sure how that can help me out. Any ideas?

• Solve separately modulo $7,11,13$ and stitch things together using the Chinese Remainder Theorem. In our case the calculation is very easy, since $420$ is special. – André Nicolas Mar 11 '14 at 5:10
• You are welcome. Sometimes one does have to compute more than a little. But usually in this type of problem we can cut down drastically on the amount of calculation. – André Nicolas Mar 11 '14 at 5:30
• Sorry, can you just specify how you would involve a congruency with mod 7, 11, 13 separately with r as a variable? I'm confused on how to actually set up the equations to follow through with the Chinese Remainder Theorem. @AndréNicolas – E 4 6 Mar 11 '14 at 6:26
• Too lengthy for a comment. Editing comments is very unpleasant, there is a $5$-minute clock. – André Nicolas Mar 11 '14 at 6:36
• Is it possible for you to explain so by submitting an answer rather than a comment? @AndréNicolas – E 4 6 Mar 11 '14 at 6:41

HINT:

As you have pointed out $1001=7\cdot11\cdot13$

Using Fermat's Little Theorem $\displaystyle314^6\equiv1\pmod7$ as $(314,7)=(6,7)=1$

$\displaystyle\implies314^{420}=(314^6)^{70}\equiv1$

Similarly, for the rest two cases

Now, lcm$(7,11,13)=?$

Formally we can use Carmichael Function, $\displaystyle\lambda(420)=60$

• We haven't covered the Carmichael Function yet so I'm sure there's another approach to this. Do you have any idea? – E 4 6 Mar 11 '14 at 5:20
• @user3358732, Are you familiar with Fermat's Little Theorem which has been used in the first method – lab bhattacharjee Mar 11 '14 at 5:22
• yes I'm familiar with it. – E 4 6 Mar 11 '14 at 5:24
• Okay I figured out how to do it using the Chinese Remainder Theorem while applying what you showed me with Fermat's Little Theorem. Thank you so much! – E 4 6 Mar 11 '14 at 5:27
• @user3358732, if you know it, you should learn mathworld.wolfram.com/EulersTotientTheorem.html and math.stackexchange.com/questions/167616/… – lab bhattacharjee Mar 11 '14 at 5:28