$\gcd(b^x - 1, b^y - 1, b^ z- 1,...) = b^{\gcd(x, y, z,...)} -1$

Question

Posible duplicado:
¿Teoría del número que pregunta?

Queridos amigos,

Desde $b$, $x$, $y$, $z$, $\ldots$ son números enteros mayores que 1, ¿cómo podemos probar que \gcd $$(b ^ x - 1, b ^ y - 1, b ^ z - 1, b \ldots)= ^ {\gcd (x, y, z,...)} - 1$$ ?

¡Gracias!

Paulo Argolo

Answer 1

Basta para comprobarlo por dos términos, es decir, $\gcd(a^n - 1, a^m - 1) = a^{\gcd(n,m)} - 1$. La idea básica es que podemos usar el algoritmo de Euclides en los exponentes, de la siguiente manera: si $n > m$, luego

$$\gcd(a^n - 1, a^m - 1) = \gcd(a^n - 1, a^n - a^{n-m}) = \gcd(a^{n-m} - 1, a^m - 1).$$

Así que podemos seguir restando un exponente de la otra hasta que llegamos $\gcd(n, m)$ como se desee. Otra manera de ver este cálculo es escribir $d = \gcd(a^n - 1, a^m - 1)$ y la nota que

$$a^n \equiv 1 \bmod d, a^m \equiv 1 \bmod d \Rightarrow a^{nx+my} \equiv 1 \bmod d$$

a partir de la cual fácilmente se deduce, como antes, que $a^{\gcd(n,m)} \equiv 1 \bmod d$, lo $d$ dividess $a^{\gcd(n,m)} - 1$. Por otro lado, $a^{\gcd(n, m)} - 1$ también se divide $d$. Para ver esto, denotan $e \cdot \gcd(n,m) = n$ $f \cdot \gcd(n,m) = m$ (verificar para yourrself que esto tiene sentido). Entonces tenemos $$\begin{align*}a^n-1 = (a^{\gcd(n,m)})^e -1 \equiv & 1 \pmod{a^{\gcd(n,m)}-1} \\ a^m-1 = (a^{\gcd(n,m)})^f-1 \equiv & 1 \pmod{a^{\gcd(n,m)}-1}. \end{align*}$$ Por lo tanto, tenemos $$a^{\gcd(n,m)}-1 \; |\; d .$$

Lo realmente interesante de este resultado es que se aplica tanto a los valores particulares de $a$ y también para $a$ como una variable, por ejemplo, en un polinomio anillo con indeterminada $a$.

Usted puede fácilmente deducir varias aparentemente trivial resultados de esta; por ejemplo, la secuencia definida por $a_0 = 2, a_n = 2^{a_{n-1}} - 1$ es una secuencia de pares de enteros primos relativos, del que se desprende que existen infinitos números primos. Trabajando sólo un poco más difícil, se puede deducir que, de hecho, hay una infinidad de números primos congruentes a $1 \bmod p$ para cualquier prime $p$.

Answer 2

Sugerencia $\,$ Por debajo de lo $\, a^M\!-\!1,\:a^N\!-\!1\ $ $\, a^{(M,N)}\!-\!1\ $ tienen el mismo conjunto $\,S$ de los comunes divisores $\,d,\,$ por lo tanto tienen el mismo mayor común divisor $\ (= \max\ S).$

$$\begin{eqnarray}\ {\rm mod}\,\ d\!:\ \ a^M,\:a^N\equiv 1&\!\iff\!\!& {\rm ord}(a)\ |\ M,N\color{#0a0}\iff {\rm ord}(a)\ |\ (M,N)\iff \color{#c00}{a^{\,(M,N)}\!\equiv 1}\\ {\rm i.e.}\ \ \ d\ |\ a^M\!-\!1,\:a^N\!-\!1 &\!\iff\!\!&\ d\ |\ \color{#c00}{a^{\,(M,N)}\!-\!1},\qquad\ \ \, {\rm where} \quad\! (M,N)\, :=\, \gcd(M,N) \end{eqnarray}$$

Comentario Nos e usa $\ a\mid b,c \color{#0a0}\iff a\mid (b,c),\,$ la fundamental característica universal de la dpc. Compare eso con la $\,\ a<b,c \!\iff\! a< \min(b,c),\ $ $\,\ a\subset b,c\iff a\subset b\cap c.\ $ universal "iff" de las caracterizaciones de permitir una rápida y fácil simultánea prueba de ambas direcciones.

La estructura conceptual, en el corazón de esta prueba simple es el omnipresente orden ideal. $\ $ Ver esta respuesta para más sobre esto, y la más conocida de la aditivo forma de un denominador ideal.

En general: $\ \gcd(f(m), f(n))\, =\, f(\gcd(m,n))\ \,$ si $\, \ f(n) \equiv f(n\!-\!m)\ \ ({\rm mod}\ f(m))\ $ $\ f(0) = 0.\,$ Ver esta respuesta para una simple prueba inductiva.

De hecho, hay un q-analógico: el resultado también es cierto para polinomios $\ f(n) = (x^n\!-\!1)/(x\!-\!1),\,$ $\ x\to 1\ $ se obtiene el entero caso (identidad de Bezout) - ver esta respuesta para una prueba simple.