Para cualquier entero$a$,$a^{37} \equiv a \left( \text{mod } 1729\right)$

Question

Para cualquier entero$a$,$a^{37} \equiv a \left( \text{mod } 1729\right).$

Se nos pide que utilicemos el teorema de Euler para demostrar esto.

Lo que he intentado:

$\phi(1729)=\phi(7)\phi(13)\phi(19)=1296$.

Si$(a,n)=1$ entonces$a^{1296} \equiv 1 \left( \text{mod } 1729\right)$. Observo que$1296=36^2$ y que algo equivalente a lo que necesito probar es$$a(a^{36}-1)\equiv 0 \left( \text{mod } 1729\right).$ $

Ahora me pregunto cuáles son las condiciones para$a^n \equiv b^n \left( \text{mod } m\right)$ que implica$a \equiv b \left( \text{mod } m\right)$, entonces puedo decir que$(a^{36})^{36} \equiv 1 (\text{mod } 1729)$ implica$a^{36} \equiv 1 (\text{mod }1729)$ en qué punto la declaración equivalente sería cierta.

Answer 1

Creo que es mejor pensar en este problema usando el teorema del resto chino. Es decir, dado que tenemos el isomorfismo de anillo$\mathbb{Z}/1729 \cong \mathbb{Z}/7 \times \mathbb{Z}/13 \times\mathbb{Z}/19$, a través del mapa$m \mapsto (m \ \mathrm{mod} \ 7, \ m \ \mathrm{mod} \ 13, \ m \ \mathrm{mod} \ 19)$, es suficiente verificar que$a^{37}=a \ \mathrm{mod} \ x$ donde$x$ es uno de$7,13$ y$19$. Pero esto se deduce del pequeño teorema de Fermat.

Answer 2

No es mucho más trabajo (y más profundas) para probar el caso general, una variante de la que caracteriza a los números de Carmichael (compuestos que se comportan como los primos de hacer en poco Fermat).

Teorema $ $ (Korselt del Pseudoprime Criterio) $\ $ $\rm\:1 < e,n\in \Bbb N\:$ hemos

$$\rm \forall\, a\in\Bbb Z\!:\ n\mid a^e\!-a\ \iff\ n\ \ is\ \ squarefree,\ \ and \ \ p\!-\!1\mid e\!-\!1\ \, for\ all \ primes\ \ p\mid n$$

Prueba de $\ \ (\Leftarrow)\ \ $ Desde un squarefree natural que divide a otro iff todos sus los factores primos de hacer, sólo necesitamos mostrar $\rm\: p\mid a^e\!-\!a\:$ para cada uno de los prime $\rm\:p\mid n,\:$ es decir que el$\rm\:a \not\equiv 0\:\Rightarrow\: a^{e-1}\equiv 1\ \ ( mod\ p),\:$, lo que, desde el $\rm\:p\!-\!1\mid e\!-1,\:$ sigue de $\rm\:a \not\equiv 0\:\Rightarrow\: a^{p-1} \equiv 1\ \ ( mod\ p),\:$ a poco de Fermat.

$(\Rightarrow)\ \ $ Que $\rm\: n\mid a^e\!-\!a\:$ todos los $\rm\:a\in\Bbb Z,\:$ debemos mostrar

$$\rm (1)\ \ n\,\ is\ squarefree,\quad and\quad (2)\ \ p\mid n\:\Rightarrow\: p\!-\!1\mid e\!-\!1$$

$(1)\ \ $ Si $\rm\,n\,$ no squarefree, a continuación, $\rm\,1\neq a^2\!\mid n\mid a^e\!-\!a \Rightarrow\: a^2\mid a\:\Rightarrow\Leftarrow$ $\rm\: (note\ \ e>1\: \Rightarrow\: a^2\mid a^e)$

$(2)\ \ $ Deje $\rm\ a\ $ ser un generador del grupo multiplicativo de a $\rm\:\Bbb Z/p.\:$ Por lo tanto $\rm\ a\ $ orden $\rm\:p\!-\!1.\:$ $\rm\:p\mid n\mid a\,(a^{e-1}\!-\!1)\:$ pero $\rm\:p\nmid a,\:$ $\rm\: a^{e-1}\!\equiv 1\,\ ( mod\ p),\:$ por lo tanto $\rm\:e\!-\!1\:$ debe ser divisible por $\rm\:p\!-\!1,\:$ el orden de $\rm\,\ a\,\ (mod\ p).\quad$ QED