Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

How will the congruence modulo works for large exponents? What theorem/s may be used? For example to show that $7^{82}$ is congruent to $9 \pmod {40}$.

share|improve this question
1  
Fermat's Little Theorem, and Chinese Remainder Theorem. –  Gerry Myerson Jul 2 '12 at 12:10
    
add comment

2 Answers

up vote 5 down vote accepted

Besides the methods mentioned by Andre, it's worth mentioning another more powerful technique that often proves crucial. Namely, instead of Euler's theorem, based on his $\phi$ (totient) function, one should use an improvement due to Carmichael, based on his $\lambda$ function (universal exponent).

The big gain in power arises from employing $\rm\:\color{#C00}{lcm}\:$ vs. product to combine exponents:

$$\begin{eqnarray}\rm a^j&\equiv&\rm 1\pmod m\\ \rm a^k&\equiv&\rm 1\pmod n\end{eqnarray}\Bigg\}\ \Rightarrow\rm\ a^{\color{#C00}{lcm}(j,k)}\equiv 1\pmod{lcm(m,n)}$$

For example, if $\rm\:n\:$ is coprime to $2,3,5$ then Euler's theorem implies that $\rm\:n^{64}\equiv 1\pmod{240},\:$ versus Carmichael's theorem, which yields the much stronger result that $\rm\:n^4\equiv 1\pmod{240}.\,$ This allows one to immediately solve the problem there, viz. $\rm\,240\:|\:p^4\!-\!1\,$ for all primes $\rm\,p > 5.$ Compare below the computation of the Euler vs. Carmichael function:

$\qquad\qquad\rm\phi(240) = \phi(2^4\cdot 3\cdot 5) = \ \phi(2^4)\ \phi(3)\ \phi(5) = 8\cdot2\cdot 4 = 64$

$\qquad\qquad\rm\lambda(240) = \lambda(2^4\cdot 3\cdot 5) = \color{#C00}{lcm}(2^{2},\phi(3),\phi(5)) = \color{#C00}{lcm}(4,2,4) = 4$

Thus Carmichael generally yields a much lower bound on the order of elements, which greatly simplifies problems like yours and that above. For more examples see my posts here.

share|improve this answer
add comment

Maybe just start calculating. Note that $7^2=49\equiv 9\pmod{40}$. So $7^4\equiv 81\equiv 1\pmod{40}$. We got lucky.

It follows that $7^{80}=(7^{16})^5\equiv 1\pmod{40}$. Thus $7^{82}=7^{80}7^2\equiv 49\equiv 9\pmod{40}$.

In general, repeated squaring, and reduction with respect to our modulus (in this case $40$) gets us to high powers fairly quickly.

A more elaborate way is to use Euler's Theorem. If $a$ is relatively prime to $m$, then $a^{\varphi(m)}\equiv 1\pmod{m}.$

Here $\varphi$ is the Euler $\phi$-function. We have $\varphi(40)=16$, so taking $a=7$ we have $a^{16}\equiv 1 \pmod{40}$. It follows that $a^{80}=(a^{16})^5\equiv 1\pmod{40}$. So $a^{82}\equiv a^2=49\pmod{40}$. But $49\equiv 9\pmod{40}$.

Still another way is to factor $40$ as $2^3\cdot 5$. We then work separately modulo $8$ and modulo $5$.

First modulo $8$: We have $7\equiv -1\pmod{8}$, so $7^{82}\equiv (-1)^{82}\equiv 1\pmod{8}$.

Next modulo $5$: We have $7\equiv 2\pmod{5}$, so $7^2\equiv 4\equiv -1\pmod{5}$, and therefore $7^4\equiv 1\pmod{5}$. (We could also get this directly by using Fermat's Theorem.) It follows that $7^{80}\equiv 1\pmod{5}$, and therefore $7^{82}\equiv 4\pmod 5$.

Now we are looking for the numbers that are congruent to $1$ modulo $8$ and to $4$ modulo $5$. For bigger numbers, we can use the Chinese Remainder Theorem. But finding a number congruent to $1$ modulo $8$ and to $4$ modulo $5$ can also be done without much machinery.

In general, the technique to use depends very much on the modulus $m$. If it is huge, and we do not know its prime factorization, then the Binary Method of exponentiation is quite efficient.

share|improve this answer
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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