1
$\begingroup$

I have a kind of confusion dealing with modular arithmetic, specially regarding remainders. I am aware of Euler/Fermat theorem that says: if p is prime, then 2^(p-1) is congruent to 1 module p.

However, supose that p is not prime. How is the best approach to compute a remainder?. For example: how to compute a remainder of 3^2348 by 25?

Thanks...

$\endgroup$
2
$\begingroup$

You must use Euler's $\varphi$ function: for any $a$ prime to $25$, $a^{\varphi(25)}=a^{20}=1$. Hence $$3^{3248}=3^{3248\bmod20}=3^8=\Bigl(\bigl(3^2\bigr)^2\Bigr)^2=6^2=11\mod25.$$

$\endgroup$
0
$\begingroup$

$3^4\equiv6\pmod{25},3^8\equiv6^2\equiv11\implies3^{10}=3^8\cdot3^2\equiv11\cdot9\equiv-1$

As $3248=325\cdot10-2,3^{3248}\equiv(-1)^{325}\cdot3^{-2}\equiv-9^{-1}\equiv11$

$\endgroup$

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.