# When Is $a^{\phi(n)+1}\equiv a \pmod n$ true?

Is $$a^{\phi(n)+1}\equiv a \pmod n$$ always true?

In what conditions is $$a^{\phi(n)+1}\equiv a \pmod n$$ true? I know that $$a^{\phi(n)+1}\equiv a \pmod n$$ is true whenever $$a$$ and $$n$$ are coprime, but it is false for a=2, n=4. What are sufficient circumstances for $$a^{\phi(n)+1}\equiv a \pmod n$$ to be true even when $$a$$ and $$b$$ are not coprime?

• No, e.g., $a=2$, $n=4$, then $\varphi(n)=2$ and $2^{2+1}\not\equiv 2\pmod{4}$. Jul 19, 2020 at 4:27
• Did you mean $a$ and $\color{red}n$ are not coprime? You want $n$ square-free Jul 19, 2020 at 4:47

A condition that is both necessary an sufficient for the congruence to hold, is that $$a$$ is coprime to $$\frac n{\gcd(a,n)}$$.

Suppose $$p|n$$ and $$p|a$$ for some prime $$p$$. Suppose $$p^i$$ is the highest power of $$p$$ that divides $$n$$. Then the property of $$p^j$$ dividing $$a$$ for $$j\leq i$$ depends only on the residue class of $$a \mod n$$.

As $$\phi(n)>0$$ for all $$n$$, we have that $$a^{\phi(n)+1}$$ will be divisible by a higher power $$j\leq i$$ of $$p$$ than $$a$$, unless $$p^i|a$$.

Repeating this argument for all primes $$p|\gcd(a,n)$$, we conclude that if $$a^{\phi(n)+1}\equiv a \mod n,$$ then $$a$$ is coprime to $$\frac n{\gcd(a,n)}$$.

Conversely if $$a$$ is coprime to $$\frac n{\gcd(a,n)}$$, write $$n=uv$$, with $$u$$ a product of primes dividing $$a$$ and $$v$$ a product of primes not dividing $$a$$. We have $$\begin{eqnarray*}a&\equiv&0 \mod u,\\a^{\phi(n)+1}&\equiv& a \mod v, \end{eqnarray*}$$ so $$a^{\phi(n)+1}\equiv a \mod n,$$ as $$u,v$$ are coprime.