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?
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.