¿Cómo puedo demostrar el teorema de Carmichael?

Question

Estoy tratando de demostrar que estas dos definiciones de la función de Carmichael son equivalentes.

Estoy usando esta definición de la función de Carmichael:

$\lambda(n)$ es el entero más pequeño tal que $k^{\lambda(n)}\equiv1 \pmod n\,$ $\forall k$ tal que $\gcd(k,n)=1$.

para probar esta otra:

$\lambda(n) = \begin{cases}\phi(p^a) & (p=2\text{ y }a\le 2)\text{ o }(p\ge 3)\\\dfrac 1 2 \phi{(2^a)} & a\ge 3\\ \text{lcm}\left((\lambda(p_1^{a_1}),\cdots,\lambda(p_k^{a_k})\right)& \text{para }n=\prod_{i=1}^k p_i^{a_i} \end{cases}$

Dado que $a^{\lambda(n)}\equiv 1 \pmod n$, y $a^{\lambda(m)}\equiv1 \pmod m$ con $\gcd(m,n)=1 \implies a^{\text{lcm}({\lambda(n)},\lambda(m)}\equiv1 \pmod {nm} $

Por lo tanto $\lambda (mn)=\text{lcm}(\lambda(n), \lambda(n))$ para $m$ y $n$ coprimos entre sí.

¿Cómo puedo demostrar las otras relaciones?

Answer 1

Necesitas probar que existen raíces primitivas $\bmod p^k$ cuando $p$ es un primo impar. Podemos hacer esto por inducción sobre $k

Para hacer esto, prueba el caso base usando el hecho de que los grupos multiplicativos de campos finitos son cíclicos y usando que $\mathbb Z_p$ es un campo.

Después de esto, pruébalo para $k=2$. Toma $a$ como una raíz primitiva $\bmod p$, el orden del subgrupo generado por $a$ de $\mathbb Z_{p^2}$ es o bien $p-1$ o $p(p-1)$ por el teorema de Lagrange y el hecho de que es un múltiplo de $p-1$ ya que es una raíz primitiva $\bmod p$.

Si no es una raíz primitiva $\bmod p^2$, entonces tenemos $a^{p-1}\equiv 1 \bmod p^2

Ahora probamos que $a+p$ es una raíz primitiva $\bmod p^2$. Esto se debe a que $(a+p)^{p-1}=a^{p-1}+(p-1)a^{p-2}p+\binom{p-1}{2}a^{p-3}p^2+\dots +p^{p-1}\equiv a^{p-1}+(p-1)a^{p-2}p\equiv 1+(p-1)a^{p-2}p\bmod p^2

Dado que $(p-1)a^{p-2}p$ no es un múltiplo de $p^2$, tenemos que $1+(p-1)a^{p-2}p$ no es $1\bmod p^2

Por lo tanto, el orden de $a+p$ no es $p-1$ y dado que $a+p$ también es una raíz primitiva $\bmod p$, concluimos que es una raíz primitiva $\bmod p^2

Ahora usamos el lema de aumento del exponente para probar que una raíz primitiva $\bmod p^2$ es una raíz primitiva $\bmod p^k$ para cualquier $k$.

Prueba: Sea $a$ una raíz primitiva $\bmod p^2$, para probar que $a$ es una raíz primitiva $\bmod p^k$ debemos probar que $a^{p^{k-2}(p-1)}\not\equiv 1\bmod p^k$. En otras palabras, debemos probar que $a^{p^{k-2}(p-1)}-1$ no es un múltiplo de $p ^k

Reescribimos esto como $a^{p^{k-2}(p-1)}-(1)^{p^{k-2}(p-1)}$ y aplicamos el lema del aumento del exponente para obtener que la potencia máxima de $p$ que divide a $a^{p^{k-2}(p-1)}-(1)^{p^{k-2}(p-1)}$ es igual a la potencia máxima de $p$ que divide a $a^{p-1}-1^{p-1}$ más la potencia máxima de $p$ que divide a $p^{k-2}$ en otras palabras $k-2+1=k-1$. Así que $p^k$ no divide a $a^{p^{k-2}(p-1)}-1$ como se deseaba.

Esto nos demuestra que $p^k$ tiene raíces primitivas para todas las potencias de primos impares. En otras palabras, esto prueba $\lambda (p^k)=(p-1)p^{k-1}$ (Porque hay $(p-1)p^k$ clases de residuos que son relativamente primos a $p$ y hemos demostrado que hay un elemento que alcanza a todos con sus potencias)

---

Probar $\lambda(2)=1$ y $\lambda (4)=2$ es fácil por inspección. Para probar $\lambda(2^k)=2^{k-2}$ también se puede hacer utilizando ideas similares a las anteriores.

Boceto de la prueba:

Observa el problema $\bmod 8$. Las clases de residuos son $1,3,5,7$ pero las potencias de cualquiera de estas clases de congruencia, $a$ son siempre $1$ y $a\bmod 8$. Esto significa que un elemento puede generar como mucho la mitad de las clases de residuos (esto se debe a que solo puede alcanzar como mucho dos de las cuatro clases $\bmod 8$). Demuestra que el elemento $3$ tiene de hecho un orden de $2^{n-2}$ y listo.