Si $a \not\equiv 1 \pmod{n}$ entonces hace $a^n \not\equiv 1 \pmod{n}$ ?

Question

Lo tenemos:
Si $a \equiv 1 \pmod{n}$ entonces hace $a^n \equiv 1 \pmod{n}$ ?

Pero no sé si esto es cierto:
Si $a \not\equiv 1 \pmod{n}$ entonces hace $a^n \not\equiv 1 \pmod{n}$ ?

Intenté encontrar un ejemplo contrario, pero siempre resultó ser cierto. ¿Alguna idea?

Gracias,

Answer 1

Piensa en la igualdad: es cierto que si $x=1$ entonces $x^n=1$ pero es pas es cierto que si $x\neq 1$ entonces $x^n\neq 1$ (por ejemplo, $x=-1$ , $n$ incluso).

Lo mismo ocurre con las congruencias: congruencias módulo $n$ pueden sumarse y multiplicarse, al igual que las igualdades: si $a\equiv b\pmod{n}$ y $c\equiv d\pmod{n}$ entonces $a+c\equiv b+d\pmod{n}$ (sumando las dos congruencias) y $ac\equiv bd\pmod{n}$ (multiplicando las dos congruencias). Lo mismo que con las igualdades. Esto da inmediatamente que si $a\equiv 1 \pmod{n}$ y multiplicando la congruencia por sí misma $m$ veces obtendrá $a^m \equiv 1^m=1\pmod{n}$ y en particular $a^n\equiv 1\pmod{n}$ .

Sin embargo, no podemos simplemente añadir y múltiples no igualdades es decir, si $a\neq b$ y $c\neq d$ entonces lo hace pas seguir que $a+c\neq b+d$ o que $ac\neq bd$ (Te dejo que encuentres contraejemplos fáciles). Fíjate bien: no son desigualdades de la forma $a\lt b$ sino simplemente de la forma "no igual a". Lo mismo ocurre con las congruencias. Sólo porque $a\not\equiv 1 \pmod{n}$ no se deduce que $a^2\not\equiv 1^2\pmod{n}$ o $a^n\not\equiv 1\pmod{n}$ en general.

Es hace seguir para $n$ primo, pero eso no se debe a las propiedades de las congruencias, sino al Pequeño Teorema de Fermat: porque el Pequeño Teorema de Fermat te dice que $a^p\equiv a\pmod{p}$ cuando $p$ es un primo, por lo que se puede concluir que si $a\not\equiv 1\pmod{p}$ entonces $a^p \equiv a\not\equiv 1\pmod{p}$ . Pero esta es una propiedad particular de los primos, no de las congruencias.

Añadido. A juzgar por los comentarios, hay situaciones en las que es cierto y otras en las que es falso:

• Si $\gcd(a,n)\gt 1$ Entonces, por supuesto $a\not\equiv 1\pmod{n}$ y de la misma manera $a^n\not\equiv 1\pmod{n}$ Se podría decir que este es el "caso trivial".

• Si $\gcd(a,n)=1$ entonces, por supuesto, tenemos $a^{\varphi(n)}\equiv 1 \pmod{n}$ por el Teorema de Euler; así, $a^n\equiv a^{\varphi(n)}a^{n-\varphi(n)}\equiv a^{n-\varphi(n)}\pmod{n}$ . Si $\gcd(\varphi(n),n-\varphi(n))=\gcd(\varphi(n),n)=1$ , entonces de $a^{n-\varphi(n)}\equiv 1\pmod{n}$ se puede concluir que $a\equiv 1\pmod{n}$ ya que ningún elemento, aparte de $1$ del grupo multiplicativo módulo $n$ tiene un orden que divide $n-\varphi(n)$ (ya que todos ellos tienen un orden que divide $\varphi(n)$ ).

• Sin embargo, si $\gcd(\varphi(n),)\gt 1$ entonces siempre podemos elegir un primo $p$ que divide $\gcd(\varphi(n),n)$ y encontrar un elemento $a$ del grupo multiplicativo módulo $n$ que tiene exactamente el orden $p$ . Eso significará que $a\not\equiv 1\pmod{n}$ pero $a^p\equiv 1\pmod{n}$ . Entonces tendremos $a^{n} = a^{\varphi(n)}a^{n-\varphi(n)} = (a^{p})^k\equiv 1\pmod{n}$ , donde $kp = n-\varphi(n)$ por lo que en este caso siempre habrá un contraejemplo.

En resumen, la implicación $$a\not\equiv 1\pmod{n}\Longrightarrow a^n\not\equiv 1\pmod{n}$$ se mantiene si y sólo si $\gcd(n,a)\gt 1$ ou $\gcd(a,n)=\gcd(\varphi(n),n)=1$ , donde $\varphi(n)$ es la función phi de Euler.

Answer 2

Contraejemplo: $a = 9$ , $n = 10$ ...

Answer 3

Esto puede ser analizado completamente por la teoría básica de grupos. Mod $\rm\:n\:$ los elementos coprimos a $\rm\:n\:$ comprenden el grupo de unidades de orden $\rm\:\phi = \phi(n)\:.\ $ Así, $\rm\ x^n = x^{\phi} = 1\ \Rightarrow\ x^{(n,\ \phi)} = 1\:.\:$ Entonces, si son coprimos, es decir $\rm\:(n,\phi)=1\:,\:$ entonces deducimos que $\rm\:x=1\:$ y el resultado es verdadero. En caso contrario, falla ya que entonces podemos elegir un primo $\rm\:p\ |\ (n,\phi)\ $ correctamente, y surge un contraejemplo eligiendo un elemento de orden $\rm\:p\:.$