Find all positive integers $n$ such that $a \equiv a^{-1} \pmod{n}$ for all invertible $a$ modulo $n$

Find all positive integers $n$ such that $a \equiv a^{-1} \pmod{n}$ for all invertible $a$ modulo $n$.

I found that $n = 1,2,4,6,8,12,24$ satisfy this. How can we prove that these are all of them?

Equivalently, you are asking that $a^2\equiv 1\pmod{n}$ for any invertible $a$ mod $n$. By the Chinese remainder theorem, it suffices to consider the case that $n=p^d$ is a prime power. If $p$ is odd and $p^d\neq3$, then $a=2$ is invertible mod $p^d$ but $a^2=4\not\equiv 1\pmod{p^d}$. If $p=2$ and $d>3$, then $a=3$ is invertible mod $p^d$ but $a^2=9\not\equiv 1\pmod{p^d}$.

So if $n$ has the property you state, then the only possible odd prime factor of $n$ is $3$ (and $3^2\not\mid n$) and the highest power of $2$ dividing $n$ is at most $2^3$. That is, $n\mid 24$, which is exactly the numbers on your list together with $n=3$ (which is also an example and is missing from your list).

• It would help to be much more precise about how you are applying CRT, since many students often stumble over matters like this. – Bill Dubuque Jan 10 '17 at 15:49

notice that this would imply $a^2\equiv 1$ for all $a$ coprime to $n$. Notice that $5$ does not work because $2^2$ is not $1\bmod 5$, we conclude that if $5|n$ then $n$ does not work.

Finally, if $5\nmid n$ then we should have that $5^2 \equiv 1 \bmod n$, which implies $n$ is a divisor of $24$.

The hypothesis implies that $U(n)$ has exponent $2$.

By the Chinese remainder theorem, the exponent of $U(n)$ is given by the Carmichael function $$\lambda (n)=\operatorname {lcm}(\lambda (p_{1}^{{a_{1}}}),\;\lambda (p_{2}^{{a_{2}}}),\dots ,\lambda (p_{k}^{a_{k}}))$$ where $$\lambda (p^a)= \begin{cases} \;\;\varphi(p^a) &\mbox{if } p\ne 2\\ \tfrac12\varphi(p^a)&\text{if }p=2 \end{cases}$$ Therefore, $\varphi(p_i^{a_i})=2$ for all odd prime factors of $n$, which implies that $p=3, a=1$ is the only possible candidate, and also that $n$ at most a factor $2^8$.

These restrictions give the list you have found.

If so, i.e. $\,(a,n)=1\,\Rightarrow\,a^{\large 2}\equiv 1\pmod{\! n},\,$ then it remains true for all divisors $\,d\mid n,\,$ hence

${\rm mod}$ odd $d\!:\, 2^{\large 2}\!\equiv 1\,\Rightarrow\ d\mid 3,\,$ so $\,n = 2^k d,\,$ where $\,\color{#c00}{d\mid 3}.\,$ Similarly

${\rm mod}\,\ \ 2^{\large k}\!:\ \ 3^{\large 2}\equiv\, 1\,\Rightarrow\, \color{#0a0}{2^{\large k}\mid 8},\,$ hence $\, n =\color{#0a0}{2^{\large k}}\color{#c00}d\mid\color{#0a0}8\cdot\color{#c00} 3=24,\,$ i.e. $\,n\mid 24$

Conversely, it is easy to prove true for $\,n = 24,\$ so it is true $\iff n\mid 24$

• Note: this is meant to show how to avoid use of CRT in Eric's answer. However, it is simpler to proceed as in Jorge's answer. But all are instructive. – Bill Dubuque Jan 10 '17 at 17:45