[Math] How to use Fermat’s theorem in congruence problems

elementary-number-theorymodular arithmetic

Two days ago I asked about how to solve questions of the type:

Find last digit of $27^{27^{26}}$.


Find the remainder when $27^{45}$ is divided by $7$, using congruences.

I have now got this method completely, but I am still not able to solve these types of questions through Fermat's theorem. If somebody can solve one of the above problem step by step through Fermat's theorem or at least can give me some hint or provide anything that can be useful for me in solving these questions (if not direct solution) then it would be of tremendous help for me.

Best Answer

I'll try my best to make it as clear as possible with an other question: Find the last digit of $7^{20}$ (next step ist, that you try to use this for your first problem):

Fermat' theorem says with $a,n$ coprime $$a^{\varphi(n)} \equiv 1 \mod n$$ With $\varphi(10)=4$ you know $7^4 \equiv 1 \mod 10$. Further more you get $7^{20} \equiv \left(7^4 \right)^5 \equiv 1 \mod 10$

So the last digit is a $1$.

Find the remainder of $27^{45} \div7$ is similar. You get $\varphi(7)=6$ and $27^6 \equiv 1 \mod 7$.

$27^{45} = 27^{6 \cdot 7 + 3} = 27^{6 \cdot 7} \cdot 27^3 = \left(27^6\right)^7 \cdot 27^3 \equiv 1^7 \cdot 27^3 \equiv 27^3 \mod 7$

I'm pretty sure you are able to solve the last equation.

Related Question