Show that $a^{25} \pmod{88}$ is congruent with $ a^{5} \pmod {88}.$

Show that $a^{25} \pmod{88}$ is congruent with $ a^{5} \pmod {88}.$

I have proved it in the case that $\gcd(88,a)=1$, but in the other case , I don't know it. Any ideas?

Solution 1:

Note that $88=11 \cdot 8$, so $\Bbb Z _{88} \simeq \Bbb Z _8 \times \Bbb Z _{11}$. Therefore, you must show that $a^{25} = a^5$ in both $\Bbb Z _8$ and $\Bbb Z _{11}$. We shall use Euler's theorem: in $\Bbb Z _n$, we have $a^{\varphi (n)} = 1$, where $\varphi$ is Euler's function. Note that $\varphi(8)=4$ and $\varphi (11)=10$.

In $\Bbb Z _{11}$, every $a \ne 0$ is coprime to $11$, so $a^{10} = a^{\varphi (11)} = 1$, so $a^{25} = a^{20+5} = (a^{10})^2 a^5 = a^5$.

In $\Bbb Z _8$, if $\gcd (a, 8) = 1$, then $a^4 = a^{\varphi (8)} = 1$, so $a^{25} = a^{24+1} = (a^4)^6 a = a$; on the other hand, $a^5 = a^{4+1} = a^4 a=a$, so $a^{25}=a^5 \mod 8$.

If $\gcd(a, 8) >1$ then $2|a$, say $a=2b$. Then $a^{25} = 2^{25} b^{25} =0$, because $8 | 2^{25}$. Similarly, $a^5 = 2^5 b^5 = 0$, so again $a^{25} = a^5$.

The last case to examine is $a=0$, but this is trivial.

Solution 2:

As $(ab)^{25}\equiv (a^{25}b^{25})\pmod{88}$, and you have the result for numbers that are relatively prime to $88$, you only need to look at the prime factors of $88=2^3\cdot 11$. $11^{25}$ is a number some calculators might find too big, but apart from that technicality it should be really easy.

Solution 3:

Since $\phi(8)=4$, if $(2,a)=1$, then $$ a^5\equiv a^{25}\pmod8\tag{1} $$ However, if $2\mid a$, then $a^5\equiv0\pmod8$ and $a^{25}\equiv0\pmod8$, so $(1)$ still holds.

Since $\phi(11)=10$, if $(11,a)=1$, then $$ a^5\equiv a^{25}\pmod{11}\tag{2} $$ However, if $11\mid a$, then $a^5\equiv0\pmod{11}$ and $a^{25}\equiv0\pmod{11}$, so $(2)$ still holds.

Putting together $(1)$ and $(2)$ gives $$ a^5\equiv a^{25}\pmod{88}\tag{3} $$