1
$\begingroup$

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?

$\endgroup$
  • 1
    $\begingroup$ 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. $\endgroup$ – André Nicolas Mar 11 '14 at 5:10
  • $\begingroup$ 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. $\endgroup$ – André Nicolas Mar 11 '14 at 5:30
  • $\begingroup$ 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 $\endgroup$ – E 4 6 Mar 11 '14 at 6:26
  • $\begingroup$ Too lengthy for a comment. Editing comments is very unpleasant, there is a $5$-minute clock. $\endgroup$ – André Nicolas Mar 11 '14 at 6:36
  • $\begingroup$ Is it possible for you to explain so by submitting an answer rather than a comment? @AndréNicolas $\endgroup$ – E 4 6 Mar 11 '14 at 6:41
1
$\begingroup$

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$

$\endgroup$
  • $\begingroup$ We haven't covered the Carmichael Function yet so I'm sure there's another approach to this. Do you have any idea? $\endgroup$ – E 4 6 Mar 11 '14 at 5:20
  • $\begingroup$ @user3358732, Are you familiar with Fermat's Little Theorem which has been used in the first method $\endgroup$ – lab bhattacharjee Mar 11 '14 at 5:22
  • $\begingroup$ yes I'm familiar with it. $\endgroup$ – E 4 6 Mar 11 '14 at 5:24
  • $\begingroup$ 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! $\endgroup$ – E 4 6 Mar 11 '14 at 5:27
  • $\begingroup$ @user3358732, if you know it, you should learn mathworld.wolfram.com/EulersTotientTheorem.html and math.stackexchange.com/questions/167616/… $\endgroup$ – lab bhattacharjee Mar 11 '14 at 5:28

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.