3
$\begingroup$

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?

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

1 Answer 1

4
$\begingroup$

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.

$\endgroup$

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .