Fermat ' s pequeño teorema falla por compuesto en lugar de números primos.

Question

Sé de Fermat Poco Teorema = Fermat-Euler Totient Teorema de al $n$ es primo.

Elementales de la Teoría de números, Jones, p83 escribe

si sólo tenemos que sustituir p con un compuesto de número entero n, el resultado de la congruencia $ a^{n-1} \equiv 1 \; (mod \, n) $ no es cierto en general. Si mcd(a, n) > 1, entonces cualquier potencia positiva de a es divisible por d, por lo que no puede ser congruente con 1 mod (n).

Por favor alguien puede amplificar estas 2 frases? Existe la intuición? Traté de probar esta -

n compuesto significa $gcd(a,n) > 1$. Dub $gcd(a,n) = g$. Por definición de g, $g|a$$g|n$.
De allí $g|a \implies g|a^k $ todos los $k \ge 1$. Entonces?

Answer 1

Si $d | n$, entonces hay un $r \in \mathbb{Z}$ tal que $dr \equiv 0 \mod n$ $n$ no divide $r$.

Supongamos, por la contradicción, no era cualquier entero $a$ tal que $ad = 1$. A continuación,$1*r \equiv adr \equiv a*0 \equiv 0 \mod n$, de modo que $n|r$.

Esto demuestra que $d$ no tiene un inverso multiplicativo modulo $n$. Por lo tanto $d^{n-1} \equiv 1 \mod n$ es imposible ya que esto implicaría que $d^{n-2}$ es un inverso multiplicativo de a $d$ modulo $n$.

El punto es que los divisores de cero no tienen inversas.

Semi-relacionada con su pregunta es este interesante fenómeno.

Answer 2

Para rellenar en el 'entonces': "entonces: $g|a^k$ y en particular $g|a^{n-1}$. Además, contamos con $g|n$ (por definición), por lo que $g$ divide cualquier combinación lineal de $a^{n-1}$ y $n$. Ya que $a^{n-1}\pmod n$ es una combinación lineal (es $1\cdot a^{n-1}-b\cdot n$, donde $b=\lfloor \frac{a^n-1}{n}\rfloor$), entonces el $g|a^{n-1}\pmod n$. "