Mostrando que$a^n - 1 \mid a^m - 1 \iff n \mid m$

Question

Que $a\ge 2$ ser un número entero. Mostrar que para enteros positivos $m,n$, tenemos $a^n - 1$divide $a^m - 1$ si y sólo si divide a $n$ $m$.

Estoy teniendo problemas con esto. He visto un problema similar por aqui pero solo muestra una dirección para la prueba. Me gustaría ver ambas direcciones.

Esto es lo que tengo hasta ahora: que $m = nq + r$, entonces el $a^m - 1 = a^{nq + r}- 1 = a^{nq}a^r - 1 = a^{nq}a^r - a^r + a^r - 1 = a^r(a^{nq} - 1) + a^r - 1$. Since $0\le r\lt n$, $r = 0$ then $a^m - 1$ = $a^{nq} - 1$ so $a^m$ = $a^{nq}$ . Así $m = nq$ por lo tanto, $n\mid m$.

Answer 1

Que $m=kn+r$. Entonces

$$(a^m-1)-(a^r-1)=a^m-a^r=a^{kn}-1=(a^n-1)(\rm junk)$$

Entonces

$$a^n-1 | a^m-1 \Leftrightarrow a^n-1 | a^r-1 \,.$$

Desde $0 \leq r <n$ tenemos $0 \leq a^r-1<a^n-1 $ y por lo tanto

$$a^n-1 | a^r-1 \Leftrightarrow a^r-1= 0 \Leftrightarrow r= 0 \Leftrightarrow n|m \,.$$

Answer 2

Podría ayudar si se piensa en escribir números enteros positivos no en base 10 ya que normalmente no, ni en base 2 o 16, como suelen hacer los ordenadores, pero en la base$a$. Entonces$a^n-1$ es un$n$ - número de dígitos en la que cada dígito es$a-1$, y de manera similar para$a^m-1$. Esto hace que sea muy fácil de ver lo que sucede cuando se aplica el algoritmo de división para dividir$a^m-1$ en$a^n-1$.

Answer 3

Aquí es otro enfoque de uso "universal identidades." Nos muestran que la primera

$$x^n -1 \mid x^m -1 \text{ in }\mathbb{Z}[x] \Longleftrightarrow n\mid m \text{ in }\mathbb{Z}.$$

Tenga en cuenta que para monic, separables polinomios $f(x),\, g(x)\in \mathbb{Z}[x]$ tenemos $f(x)\mid g(x)$ fib cada raíz de $f(x)$ $\mathbb{C}$ también es una raíz de $g(x)$. Tenga en cuenta que $x^n-1$ es divisible por todos los $n\in\mathbb{N}$, lo que sigue a partir de la $\gcd(x^n-1,nx^{n-1})=1$$\mathbb{Z}[x]$.

Primero supongamos $n\mid m$. Deje $x_0$ ser una raíz de $x^n-1$$\mathbb{C}$. A continuación, $m =nk$ algunos $k\in \mathbb{Z}$, y tenemos $x_0^m = x_0^{nk} = 1^k = 1$. Por eso, $x_0^m-1 = 0$. Por lo tanto, $x^n-1 \mid x^m-1$.

Siguiente, supongamos $x^n-1 \mid x^m-1$. Deje $x_0$ ser una primitiva $n$th raíz de la unidad (no $k$th raíz de la unidad para cualquier $k<n$) que existe siempre (el ejercicio.) Por el algoritmo de la división, podemos escribir $m = nq + r$ donde$q,\,r\in \mathbb{Z}$$0\leq r < n$. Por nuestra suposición, $1 = x_0^m = x_0^{nq + r} = x_0^r$. Desde que asumió $x_0$ primitiva, $r=0$. Por lo tanto, $m = nq$$n\mid m$.

Ahora que hemos establecido la equivalencia en $\mathbb{Z}[x]$, se puede aplicar una evaluación homomorphism en cualquier entero $a$ conseguir $n\mid m \Longrightarrow a^n-1 \mid a^m-1$. Yo no ver rápidamente si podemos obtener la inversa de la implicación de este argumento. En cualquier caso, la idea era demostrar una cuidada técnica.