Encuentre todos los enteros positivos$n$ de manera tal que$a \equiv a^{-1} \pmod{n}$ para todos los invertibles$a$ modulo$n$

Question

Encuentre todos los enteros positivos$n$ de manera tal que$a \equiv a^{-1} \pmod{n}$ para todos los invertibles$a$ modulo$n$.

Encontré que$n = 1,2,4,6,8,12,24$ satisface esto. ¿Cómo podemos probar que estos son todos ellos?

Answer 1

Equivalentemente, están pidiendo $a^2\equiv 1\pmod{n}$ para cualquier invertible $a$ mod $n$. Por el teorema del resto Chino, es suficiente con considerar el caso de que $n=p^d$ es una fuente primaria de energía. Si $p$ es impar y $p^d\neq3$, $a=2$ es invertible mod $p^d$ pero $a^2=4\not\equiv 1\pmod{p^d}$. Si $p=2$$d>3$, $a=3$ es invertible mod $p^d$ pero $a^2=9\not\equiv 1\pmod{p^d}$.

Así que si $n$ tiene la propiedad que el estado, entonces la única posible impar primer factor de $n$ $3$ (e $3^2\not\mid n$) y el más alto poder de $2$ dividiendo $n$ es en la mayoría de las $2^3$. Es decir, $n\mid 24$, que es exactamente los números en su lista, junto con $n=3$ (que es también un ejemplo y se encuentra en su lista).

Answer 2

observe que esto implicaría$a^2\equiv 1$ para todos$a$ coprime a$n$. Tenga en cuenta que$5$ no funciona porque$2^2$ no es$1\bmod 5$, concluimos que si$5|n$ entonces$n$ no funciona.

Finalmente, si$5\nmid n$ entonces deberíamos tener ese$5^2 \equiv 1 \bmod n$, lo que implica que$n$ es un divisor de$24$.

Answer 3

La hipótesis implica que $U(n)$ ha exponente $2$.

Por el teorema del resto Chino, el exponente de $U(n)$ está dado por el Carmichael función $$\lambda (n)=\operatorname {lcm}(\lambda (p_{1}^{{a_{1}}}),\;\lambda (p_{2}^{{a_{2}}}),\dots ,\lambda (p_{k}^{a_{k}}))$$ donde $$\lambda (p^a)= \begin{cases} \;\;\varphi(p^a) &\mbox{if } p\ne 2\\ \tfrac12\varphi(p^a)&\text{if }p=2 \end{casos}$$ Por lo tanto, $\varphi(p_i^{a_i})=2$ para todos los impares factores primos de a $n$, lo que implica que $p=3, a=1$ es el único candidato posible, y también que $n$ a más de un factor de $2^8$.

Estas restricciones dar la lista que usted ha encontrado.

Answer 4

Si es así, es decir,$\,(a,n)=1\,\Rightarrow\,a^{\large 2}\equiv 1\pmod{\! n},\,$ entonces sigue siendo cierto para todos los divisores$\,d\mid n,\,$ por lo tanto

${\rm mod}$ imp$d\!:\, 2^{\large 2}\!\equiv 1\,\Rightarrow\ d\mid 3,\,$% así que$\,n = 2^k d,\,$ donde$\,\color{#c00}{d\mid 3}.\,$ de manera similar

${\rm mod}\,\ \ 2^{\large k}\!:\ \ 3^{\large 2}\equiv\, 1\,\Rightarrow\, \color{#0a0}{2^{\large k}\mid 8},\,$ por lo tanto$\, n =\color{#0a0}{2^{\large k}}\color{#c00}d\mid\color{#0a0}8\cdot\color{#c00} 3=24,\,$ ie$\,n\mid 24$

A la inversa, es fácil demostrar que es cierto para$\,n = 24,\ $ por lo que es cierto$\iff n\mid 24$