# Proving that $a^{25}$ mod 65 = $a$ mod 65 [duplicate]

I think that I got the answer, but am not quite sure whether or not it is correct.

Prove that $$a^{25}$$ mod 65 = $$a$$ mod 65 given that $$a \in \mathbb{Z}$$

I started off by using the Chinese Remainder Theorem (65 = 5 $$\cdot$$ 13 and gcd(5, 13) = 1) in order to get the following two equations:

$$a^{25}$$ mod 5 = $$a$$ mod 5

and

$$a^{25}$$ mod 13 = $$a$$ mod 13

After that, I used the theorem that states that:

$$a^e \equiv a^{e \textrm{ mod } \phi(n)} \textrm{ mod } n$$ if gcd(a, n) = 1

$$\phi(5) = 4$$ and $$\phi(13) = 12$$

Applying said theorem to the two equations above:

$$a^{25 \textrm{ mod } 4}$$ mod 5 = $$a^1$$ mod 5 = $$a$$ mod 5

and

$$a^{25 \textrm{ mod } 12}$$ mod 13 = $$a^1$$ mod 13 = $$a$$ mod 13

I know that the theorem states that gcd(a, n) = 1 which isn't necessarily the case, that's why I wasn't sure whether my solution was correct.

• What do you know about $a$? – Bernard Apr 30 at 20:31
• @Bernard I only know that $a \in \mathbb{Z}$, forgot to mention it in the post, will edit it now – mrMoonpenguin Apr 30 at 20:33

For prime $$n$$, we have $$a^n\equiv a\pmod n$$. This doesn't require any sort of assumption on the relationship between $$a$$ and $$n$$ (we can deduce it from your result for $$\gcd(a,n)=1$$, and for $$\gcd(a,n)=n$$, well, $$0^n\equiv 0$$ is obvious).

Modulo $$5$$ we get $$a^{25}=(a^5)^5\equiv a^5\equiv a$$Modulo $$13$$ we get $$a^{25}=a^{13}\cdot a^{12}\equiv a\cdot a^{12}\equiv a$$

• Good answer. And to emphasize for $a \equiv 0$ mod 5 it follws that $a^{25} \equiv 0$ mod 5 $\equiv$ $a$ mod 5.... – Mike Apr 30 at 20:37
• Right, thanks! I assume that this is a variation of Fermat's little theorem? – mrMoonpenguin Apr 30 at 20:41
• @mrMoonpenguin Yes, it is a special case of a generalization of Fermat & Euler's theorem - see my answer in the linked dupe and see the 2nd dupe thread for other methods (applied to a similar problem). – Bill Dubuque Apr 30 at 21:22