La función φ de Euler y Euler ' teorema s

Question

Esta es una duda muy elemental.

Es cierto que, $\phi(n)$ el número más pequeño que $a^{\phi(n)} \equiv 1 \pmod n$, donde $\gcd(a,n)=1$.

Answer 1

No; no es el más pequeño de los valores específicos de $a$; ni siquiera el más pequeño que funciona para todas las $a$.

Por ejemplo, $\phi(8) = 4$, pero para todo entero impar $n$, $n^2\equiv 1 \pmod{8}$.

El número que usted está buscando se llama la "reducción de la totient función", "menos universal exponente de la función", o Carmichael función de $\lambda(n)$. Este es el menor entero positivo tal que para todos los $a$ $\gcd(a,n)=1$ ,$a^{\lambda(n)}\equiv 1\pmod{n}$. Siempre divide $\phi(n)$.