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}$.
Answer
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.
No comments:
Post a Comment