4
$\begingroup$

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?

$\endgroup$
4
$\begingroup$

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

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

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

$\endgroup$
1
$\begingroup$

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.

$\endgroup$
1
$\begingroup$

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$

$\endgroup$
  • $\begingroup$ 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. $\endgroup$ – Bill Dubuque Jan 10 '17 at 17:45

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.