Dado un número entero [math] n [/ math] que es mayor que [math] 1 [/ math], ¿qué es [math] \ gcd (2 ^ n – 1, 3 ^ n – 1, \ ldots, n ^ n – 1) [/ matemáticas]?

Answer 1

Buena pregunta.

Primero, experimentamos y observamos.

• Cuando [math] n = 2 [/ math] solo tenemos un número aquí, y es [math] 3 [/ math].
• Cuando [math] n = 3 [/ math] buscamos el mcd de [math] 7 [/ math] y [math] 26 [/ math]. Es simplemente [matemáticas] 1 [/ matemáticas]. Esos números son relativamente primos.
• Cuando [matemática] n = 4 [/ matemática] tenemos [matemática] 15 [/ matemática], [matemática] 80 [/ matemática] y [matemática] 255 [/ matemática]. Todos divisibles por [matemáticas] 5 [/ matemáticas] y ningún otro divisor común, por lo que la respuesta es [matemáticas] 5 [/ matemáticas].

En este punto deberíamos notar algo. ¿Cómo es que los números [matemática] a ^ 4-1 [/ matemática] son ​​divisibles por [matemática] 5 [/ matemática] para [matemática] a = 2,3,4 [/ matemática]? ¿Sonar una campana? Claro, ese es el pequeño teorema de Fermat para el primer [matemáticas] p = 5 [/ matemáticas].

En general, si [math] p [/ math] es un número primo y [math] n = p-1 [/ math], sabemos que todos los números [math] a ^ n-1 [/ math] son de hecho divisible por [matemática] p [/ matemática] siempre que [matemática] a [/ matemática] no sea divisible por [matemática] p [/ matemática], que es precisamente el caso de los números entre [matemática] 2 [/ math] y [math] n = p-1 [/ math].

Ahora estamos en condiciones de hacer una conjetura: el máximo común divisor de los números [matemática] 2 ^ n-1 [/ matemática], [matemática] 3 ^ n-1 [/ matemática] y así sucesivamente hasta [matemática] n ^ n-1 [/ math] es [math] n + 1 [/ math], si [math] n + 1 [/ math] es primo, o si no es solo [math] 1 [/ math ]

Verificar esto por algunos valores más parece confirmar nuestra sospecha. Cuando [math] n = 5 [/ math] encontramos que el mcd es [math] 1 [/ math], mientras que para [math] n = 6 [/ math] es exactamente [math] 7 [/ math].

Además, ya sabemos que el mcd es al menos [matemática] p [/ matemática] cuando [matemática] n + 1 = p [/ matemática] es primo. Lo que aún tenemos que hacer es demostrar que no hay otros primos [matemáticos] q [/ matemáticos] disponibles, dividiendo todos esos números [matemáticos] a ^ n-1 [/ matemáticos], y además que los primos [matemáticos] p [/ math] divide nuestro mcd solo una vez (entonces [math] p ^ 2 [/ math] no lo divide).

---

La forma en que preferí ver esto no es necesariamente la más elemental, pero creo que es la más esclarecedora. Siempre prefiero pensar en el pequeño teorema de Fermat y asuntos relacionados como declaraciones sobre el campo finito [math] \ mathbb {F} _p = \ mathbb {Z} / p \ mathbb {Z} [/ math] y polinomios sobre él.

Por ejemplo, dado que el grupo multiplicativo de [math] \ mathbb {F} _p [/ math] tiene elementos [math] p-1 [/ math], cada elemento distinto de cero tiene un orden que divide [math] p-1 [/ math] , entonces [math] X ^ {p-1} [/ math] siempre se evalúa como [math] 1 [/ math] cuando sustituye elementos de campo distintos de cero por [math] X [/ math]. En otras palabras, este polinomio [matemático] X ^ {p-1} -1 [/ matemático] tiene todos los residuos [matemático] 1,2, \ ldots, p-1 [/ matemático] como raíces, por lo que simplemente se factoriza como

[matemáticas] X ^ {p-1} -1 = (X-1) (X-2) \ ldots (X- (p-1)) [/ matemáticas]

que debe entenderse como una igualdad entre polinomios sobre [math] \ mathbb {F} _p [/ math].

Esta es una manera rápida y fácil de ver por qué el pequeño teorema de Fermat es cierto. Pero estamos en una situación ligeramente diferente: ¿podría ser que todos esos residuos [matemática] 1,2,3, \ ldots, n [/ matemática] serían raíces de [matemática] X ^ n-1 [/ matemática] en algún otro campo finito [math] \ mathbb {F} _q [/ math], cuando [math] q [/ math] es un primo diferente de [math] n + 1 = p [/ math]?

Bueno, ciertamente debemos tener [math] q> p [/ math], ya que [math] q <p [/ math] hace que [math] q [/ math] sea uno de los números entre [math] 1 [/ math] y [math] n [/ math], por lo que [math] q ^ n-1 [/ math] no puede desaparecer mod [math] q [/ math].

Así que ahora tenemos un gran campo finito [math] \ mathbb {F} _q [/ math], y sobre él estamos viendo el polinomio [math] X ^ n-1 [/ math], y nos preguntamos si es es posible que milagrosamente este polinomio se divida en [matemáticas] n [/ matemáticas] raíces distintas que resultan ser los residuos [matemáticas] 1,2,3, \ ldots, \ n [/ matemáticas] módulo [matemáticas] q [/ matemáticas ] Bastante extravagante, ¿verdad? ¿Pero por qué no puede ser verdad?

Bueno, si así fuera, entonces tendríamos una factorización de polinomias nuevamente

[matemáticas] X ^ n-1 = (X-1) (X-2) \ ldots (Xn) [/ matemáticas]

esta vez modulo [math] q [/ math]. Expandiendo el lado derecho y comparando coeficientes, encontramos que el coeficiente de [matemáticas] X ^ n [/ matemáticas] está bien, el coeficiente libre es [matemáticas] (- 1) ^ nn! [/ Matemáticas] (de donde usted puede derivar rápidamente el teorema de Wilson) y es difícil saber si es o no [matemática] -1 [/ matemática] módulo [matemática] q [/ matemática] por lo que no ayuda, pero el siguiente coeficiente que debe verificar es el siguiente al líder, el coeficiente de [matemáticas] X ^ {n-1} [/ matemáticas]. Esto es cero en el lado izquierdo, pero en el derecho es [matemática] \ frac {n (n + 1)} {2} [/ matemática], que de hecho es divisible por [matemática] p = n + 1 [/ matemática] pero no por ninguna [matemática] q [/ matemática] mayor que [matemática] p [/ matemática] (y tampoco debe ser [matemática] p ^ 2 [/ matemática], lo que también deja descansar lo importante).

Por lo tanto, esta identidad polinomial solo tiene un módulo [matemático] p = n + 1 [/ matemático] cuando [matemático] n + 1 [/ matemático] es primo, y no módulo ningún otro primo. Por lo tanto, el único primo disponible para dividir nuestro mcd es [matemática] p = n + 1 [/ matemática] (si existe), y está disponible solo una vez, por lo que se demuestra nuestra conjetura. QED

---

Por otro lado, este es otro ejemplo divertido de una simple “fórmula” para la primacía. Acabamos de demostrar que la magnitud

[matemáticas] \ chi (n) = (\ gcd (2 ^ n-1,3 ^ n-1, \ ldots, n ^ n-1) -1) / n [/ math]

satisface [matemáticas] \ chi (n) = 1 [/ matemáticas] si [matemáticas] n + 1 [/ matemáticas] es primo y [matemáticas] \ chi (n) = 0 [/ matemáticas] si no lo es. Una pregunta frecuente en matemáticas es “¿cuál es la fórmula para los números primos?” [1], así que aquí está (otra).

Notas al pie

[1] ¿Cuál es la fórmula de los números primos?

Answer 2

Para comprender el resultado, necesitará el pequeño teorema de Fermat.

Si [math] p [/ math] es primo y [math] a [/ math] es un número entero, [math] a ^ {(p-1)} – 1 [/ math] es divisible por [math] p [/ matemáticas].

Entonces, si en su expresión, [matemática] n + 1 [/ matemática] es primo, todos los números serán divisibles por [matemática] n + 1 [/ matemática] y el MCD será [matemática] n + 1 [/ matemáticas].

Si [math] n + 1 [/ math] no es primo y es mayor que 2, el resultado debería ser [math] 1 [/ math].

Answer 3

Primero supongamos que [math] \ gcd [/ math] no es [math] 1 [/ math]. Entonces, existe un primer [matemáticas] p [/ matemáticas] tal que [matemáticas] p | \ gcd (2 ^ n – 1, 3 ^ n – 1, \ ldots, n ^ n – 1) [/ math]. Como [math] p [/ math] divide la [math] \ gcd [/ math], sabemos que

[matemáticas] 2 ^ n \ equiv 1 \ mod {p}, 3 ^ n \ equiv 1 \ mod {p}, \ ldots \ tag * {} [/ matemáticas]

Ahora, si [math] p \ leq n [/ math], entonces [math] p [/ math] debe haber sido uno de los números desde [math] 2 [/ math] a [math] n [/ math] nosotros que [math] p ^ n \ equiv 1 \ mod {p} [/ math] que es definitivamente falso. Entonces, [math] \ gcd [/ math] es [math] 1 [/ math] if [math] p \ leq n [/ math].

Observe que si [math] p = n + 1 [/ math] es primo, entonces [math] p | \ gcd (2 ^ n – 1, 3 ^ n – 1, \ ldots, n ^ n – 1) [/ math] por el pequeño teorema de Fermat. Ahora supongamos que [math] p> n [/ math]. Anteriormente, sabíamos que [math] x ^ n \ equiv 1 \ mod {p} [/ math] tiene soluciones [math] 1,2, \ ldots, n [/ math] que son pares mod [math] p [ /matemáticas]. Por el teorema de Lagrange, tenemos que

[matemáticas] x ^ n – 1 \ equiv (x-1) (x-2) \ ldots (xn) \ mod {p} \ tag * {} [/ matemáticas]

Ahora, si miramos el coeficiente de [matemáticas] x ^ {n-1} [/ matemáticas] en ambos lados, obtenemos que

[matemáticas] 0 \ equiv -1 -2 -3 \ ldots -n \ mod {p} \ tag * {} [/ matemáticas]

lo que implica que [matemáticas] p | \ frac {n (n + 1)} {2} [/ matemáticas]. Como [math] p> n [/ math], obtenemos que [math] p = n + 1 [/ math]. Por lo tanto, [math] \ gcd [/ math] es [math] 1 [/ math] si [math] n + 1 [/ math] no es primo y [math] p ^ {\ alpha} [/ math ] si [matemáticas] p = n + 1 [/ matemáticas].

Ahora, intentemos encontrar [math] \ alpha [/ math]. Suponiendo que [matemáticas] p = n + 1 [/ matemáticas], sabemos que [matemáticas] p ^ {\ alpha} | (p-1) ^ {p-1} – 1 [/ math] porque [math] n = p-1 [/ math]. Usando el teorema binomial y tomándolo mod [math] p ^ 2 [/ math], tenemos que

[matemáticas] p ^ {\ alpha} | (p-1) ^ {p-1} – 1 \ equiv (-1) ^ {p-1} + {{p-1} \ elegir {1}} (- 1) ^ {p-2} p – 1 \ mod {p ^ 2} \ tag * {} [/ math]

porque todas las otras partes de la expansión binomial tienen un factor de [matemáticas] p ^ 2 [/ matemáticas]. Finalmente, expandir el RHS da [math] -p (p-1) [/ math] que es equivalente a [math] p [/ math] mod [math] p ^ 2 [/ math]. Entonces, [math] p ^ {\ alpha} \ equiv p \ mod {p ^ 2} [/ math] implica que [math] \ alpha = 1 [/ math].

Resumiendo, [matemáticas] \ gcd (2 ^ n – 1, 3 ^ n – 1, \ ldots, n ^ n – 1) [/ matemáticas] es igual a [matemáticas] 1 [/ matemáticas] si [matemáticas] n + 1 [/ math] no es primo y es igual a [math] n + 1 [/ math] si [math] n + 1 [/ math] es un primo.