Remainder of $15^{81}$ divided by $13$ without using Fermat's Little theorem.

Question

I was requested to find the congruence of $15^{81}mod{13}$ without using Fermat's theorem (since that is covered in the chapter that follows this exercise). Of course I know that by property $15^{81} equiv 2^{81} pmod{13}$, but how could I find what is the congruence of $2^{81}$ without using Fermat? Needless it is to say that an exhaustive iterative method would be extremely long.

Sil · Answer

We can for example use $15=3 cdot 5$ and notice $3^3=27 equiv 1 bmod 13$, and $5^2=25 equiv -1 bmod 13$. So
$$
15^{81}=3^{81}5^{81}=(3^{3})^{27}(5^2)^{40}5equiv 1^{27}(-1)^{40}5=5 pmod{13}.
$$

Don Thousand · Answer

$15equiv2bmod13$, so we have $$15^{81}equiv2^{81}bmod{13}$$$$equiv512^9equiv5^9bmod{13}$$$$equiv125^3equiv8^3bmod{13}$$$$equiv512equiv5bmod13$$

Remainder of $15^{81}$ divided by $13$ without using Fermat's Little theorem.

2 Answers

Add your own answers!

Ask a Question