0
$\begingroup$

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.

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

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$$

$\endgroup$
  • 1
    $\begingroup$ Good answer. And to emphasize for $a \equiv 0$ mod 5 it follws that $a^{25} \equiv 0$ mod 5 $\equiv$ $a$ mod 5.... $\endgroup$ – Mike Apr 30 at 20:37
  • $\begingroup$ Right, thanks! I assume that this is a variation of Fermat's little theorem? $\endgroup$ – mrMoonpenguin Apr 30 at 20:41
  • 1
    $\begingroup$ @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). $\endgroup$ – Bill Dubuque Apr 30 at 21:22

Not the answer you're looking for? Browse other questions tagged or ask your own question.