Demostrar que si $k\ge 1\,$ y $\,a^k\equiv 1\pmod{\! n}$ entonces $\gcd(a,n)=1$

Question

Dejemos que $p$ sea un primo tal que $a^p-1 \equiv 0 \pmod{p}$ . Demostrar que $\gcd(a,p) = 1$ .

Sabemos por el Pequeño Teorema de Fermat que $a^{p-1}-1 \equiv 0 \pmod{p}$ si y sólo si $\gcd(a,p) = 1$ Pero, ¿cómo podemos utilizar esto para resolver la cuestión?

Answer 1

Supongamos que $\gcd(a,p) \neq 1$ . Es decir, asumir que $p$ divide $a$ . Es decir, hay un $m$ tal que $a = mp$ . Entonces $$ a^{p} - 1 = (mp)^p - 1 = m^pp^p - 1 \equiv -1 \pmod{p}. $$

Answer 2

Es una pregunta un poco impar, pero si realmente quieres saber esto:

Como ha comentado correctamente $a^{p-1} -1 \equiv 0 \pmod{p}$ para $\gcd(a,p)=1$ . De ello se desprende que $a^{p} -a \equiv 0 \pmod{p}$ para aquellos $a$ . Y si $\gcd(a,p)\neq 1$ entonces es $p$ y por lo tanto $a^{p} -a \equiv 0 \pmod{p}$ también en ese caso como $a$ mismo es $0 \pmod{p}$ .

Así, $a^{p}-a \equiv 0 \pmod{p}$ para todos $a$ . Por lo tanto, $a^{p}-1 \equiv 0 \pmod{p}$ si y sólo si $a-1 \equiv 0 \pmod{p}$ es decir $a \equiv 1 \pmod{p}$ . Esto implica, en particular, que $\gcd(a,p)=1$ .

(Es posible que la pregunta estuviera pensada con $p-1$ en lugar de $p$ pero eso es parte del pequeño teorema de Fermat, así que lo sabes de todos modos).

Answer 3

Incluso más es cierto:

Si $a$ y $b$ son números enteros y $n\in\mathbb N^+$ tal que $a^n-1\equiv 0\pmod b$ entonces $\gcd(a,b)=1$ .

Lo que se quiere es entonces el caso especial en el que $n$ y $b$ ambos resultan ser iguales al mismo primo.

Prueba. $a^n-1\equiv 0 \pmod b$ significa que hay $k$ tal que $a^n-1=kb$ que es lo mismo que $a^{n-1}a+(-k)b=1$ Así que por la identidad de Bezout $\gcd(a,b)$ debe ser $1$ .

Answer 4

Espero que la notación de barras pueda facilitar el asunto:

En el campo $\mathbb{Z}/p\mathbb{Z}$ la ecuación $a^p-1\equiv 0 \pmod{ p}$ simplemente significa

$\displaystyle\left(\overline{a}\right)^p=\overline{1}$ .

Y $\gcd(a,p)=1$ si y sólo si $\overline{a}\neq\overline{0}$ , lo cual es bastante obvio a partir de la ecuación anterior.

Answer 5

No dejes que la memorización de teoremas te haga perder el sentido común.

Si $p$ es primo, los únicos números que no son relativamente primos son los múltiplos de $p$ y $(kp)^p \equiv 0 \mod p$ .

\=======

A lejos resultado más fuerte sería $ma -1 \equiv \mod p \implies \gcd(a,p) = 1$ independientemente de que $p$ es primo o no o si $m = a^{p-1}$ o cualquier número.

¡Oh, y duh! Si $a^p = 1 \mod p$ entonces $a \equiv 1 \mod p$ . Esa es una cuestión mucho más interesante y menos trivial.