Demostrar que $k|φ(m)$

Question

Supongamos que $a$ y $m$ son relativamente primos y $k$ es el menor número natural que $a^k\equiv1\mod m$ . Demostrar que $k|φ(m)$ .

Esto es sólo una variación del Teorema de Fermat, ¿Así que sólo tengo que demostrar que $k = m-1$ y cómo $\varphi(m) = (k)(x)$ ? No sé de qué otra manera probarlo

Answer 1

Si $\gcd(a,m)=1,$ entonces $a\in U_m,$ donde $U_m$ es el grupo de unidades en $\mathbb{Z}_m.$ Así que utiliza estos datos:

• $|U_m|=\varphi(m)$
• $a\in G\implies |a|\;\text{divides}\; |G|$

Answer 2

Dejemos que $G=U(\Bbb Z/m)$ . Sabemos que $|G|=\phi(m)$ . El orden del elemento $a\in G$ divide el orden del grupo de Lagrange. Ahora tenemos $a^k=1$ en este grupo, con $k$ mínimo. Esto significa que $ord(a)=k$ . Por lo tanto, $k\mid \phi(m)$ .

Answer 3

Sabes por el teorema de Euler (no FLT porque no sabemos que $m$ es primo) que $a^{\phi(m)} \equiv 1 \pmod m$ .

Pero no sabemos que $\phi(m)$ es el número más pequeño y es fácil encontrar ejemplos en los que no lo es. Digamos que $2^3 \equiv 1 \pmod 7$ entonces $3 \ne \phi (7) = 6$ pero sabemos que $3|6$ .

Esto es lo que debes tener en cuenta.

1: Si $a^j \equiv b \pmod m$ y $a^K \equiv 1$ entonces $a^{K+j} \equiv a^Ka^j \equiv a^j \equiv b\pmod m$ .

Entonces 1b: Si $a^k \equiv 1\pmod m$ y $n > k$ entonces $a^n = a^{n-k}a^k \equiv a^{n-k}*1 \equiv a^{n-k}\pmod m$ .

Y PISTA: Si $a^k \equiv 1\pmod m$ y $a^n \equiv 1 \pmod m; n > k$ entonces qué es $a^{n - k}\equiv ? \pmod m$ . Pista a la PISTA: $a^{n-k}*a^k= a^n$ .

!!!GRAN PISTA!!!!

$k \le \phi(m)$ . Sea $\phi(m) = nk + r; r < k$ .

Pista para el !!!GRAN PISTA!!!!

Así que $1= a^{\phi(m)} \equiv a^{nk}a^r \equiv a^r\pmod m$ .