Tuesday, 17 March 2026

Exercise (5.2).11

For the following either give a proof or exhibit a counterexample:

Let $\gcd (a, n) = 1$ then

$$ a^{\phi(\phi(n))} ≡ 1 \pmod n $$


Consider $a=3, n=5$, which means $\gcd(3,5)=1$.

We have $\phi(5)=4$, and so $\phi(\phi(5)) = \phi(4) = 2$.

And so

$$ \begin{align} a^{\phi(\phi(n))} & \equiv  3^{2} \pmod 5 \\ \\ & \equiv 9 \pmod 5 \\ \\ & \equiv 4 \pmod 5 \\ \\ a^{\phi(\phi(n))} & \not \equiv 1 \pmod n \end{align}$$

This is a counter-example to the given proposition.