Cómo demostrar que para cada entero positivo n, [matemáticas] 2 ^ n \ not \ equiv 1 \ pmod {n} [/ matemáticas]

Answer 1

Como se dijo, este problema es falso; [math] n = 1 [/ math] proporciona un contraejemplo. Entonces supondré [matemáticas] n> 1 [/ matemáticas] .

Supongamos que hay un número entero positivo [matemática] n> 1 [/ matemática] tal que [matemática] n \ mid (2 ^ n-1) [/ matemática]. Tenga en cuenta que [math] n [/ math] debe ser impar , ya que [math] 2 ^ n-1 [/ math] es impar . Deje que [math] \ ell [/ math] denote el menor entero positivo mayor que [math] 1 [/ math] que satisface [math] \ ell \ mid (2 ^ {\ ell} -1) [/ math]. Como [math] \ gcd (2, \ ell) = 1 [/ math], tenemos [math] \ ell \ mid (2 ^ {\ phi (\ ell)} – 1) [/ math].

Recuerde que [math] \ gcd (2 ^ r-1,2 ^ s-1) = 2 ^ {\ gcd (r, s)} – 1 [/ math]. Esto ha sido publicado en Quora. En realidad, todo lo que necesitamos repetidamente aquí es que [matemática] 2 ^ {\ gcd (r, s)} – 1 [/ matemática] divide tanto [matemática] 2 ^ r-1 [/ matemática] como [matemática] 2 ^ s -1 [/ matemáticas]. La última divisibilidad se deduce del hecho de que [matemática] x-1 [/ matemática] divide [matemática] x ^ m-1 [/ matemática] como un polinomio, para cada entero positivo [matemática] m [/ matemática]. Ahora ponga [math] x = 2 ^ {\ gcd (r, s)}, [/ math] y observe que [math] \ gcd (r, s) [/ math] divide ambos [math] r [/ math] y [matemáticas] s [/ matemáticas].

Por lo tanto, de [math] \ ell [/ math] dividiendo tanto [math] 2 ^ {\ ell} -1 [/ math] como [math] 2 ^ {\ phi (\ ell)} – 1 [/ math], concluimos que [math] \ ell [/ math] divide [math] 2 ^ g-1 [/ math], donde [math] g = \ gcd (\ ell, \ phi (\ ell)) [/ math]. Entonces

[matemáticas] g \ mid \ ell [/ matemáticas] y [matemáticas] \ ell \ mid (2 ^ g-1) [/ matemáticas],

así que eso

[matemáticas] g \ mid (2 ^ g-1) [/ matemáticas]. Esto contradice la minimidad de [math] \ ell [/ math], ya que [math] 1 <g \ le \ phi (\ ell) 1 [/ math] por suposición). Por lo tanto, no existe ningún número entero [math] n [/ math] mayor que [math] 1 [/ math] que satisfaga [math] n \ mid (2 ^ n-1) [/ math]. QED

Answer 2

En primer lugar, permítanme indicar un resultado común relacionado con su pregunta. Para cada entero [matemáticas] n [/ matemáticas], lo que sabemos es que [matemáticas] 2 ^ {\ phi (n)} \ equiv 1 \ pmod {n} [/ matemáticas], donde [matemáticas] \ phi (n ) [/ math] es la función totient de Euler.

Si [math] n = p [/ math] es primo, entonces [math] 2 ^ {p-1} \ equiv 1 \ pmod {p} [/ math], de modo que [math] 2 ^ {p} \ equiv 2 \ pmod {p} [/ math]. Esa es la prueba.

Pero, la afirmación [matemáticas] 2 ^ n \ not \ equiv 1 \ pmod {n} [/ matemáticas] puede no ser válida. El siguiente ejemplo obvio es en el caso [math] n = p ^ a [/ math], donde p es primo y [math] a> 1 [/ math] es un entero positivo. Este caso me da la sensación de que a veces puede ser válido, pero no siempre es válido. Recuerde que [math] \ phi (n) = p ^ a (p-1) [/ math] y [math] 2 ^ {\ phi (n)} \ equiv 1 \ pmod {n} [/ math]. Se deduce que [matemáticas] 2 ^ {n} = 2 ^ {n – \ phi (n)} = 2 ^ {p ^ {a} -p ^ {a-1} (p-1)} = 2 ^ { p ^ {a-1}} \ pmod {n} [/ math]. La última expresión podría ser congruente con [math] 1 [/ math] o no [math] 1 [/ math]. Creo que cualquiera de los casos es posible ya que estás hablando de cada número entero [math] n [/ math].

Permítanme intentar asumiendo que, por el contrario, que [matemáticas] 2 ^ n \ equiv 1 \ pmod {n} [/ matemáticas]. De la fórmula en la primera línea anterior, obtendríamos [math] 2 ^ {\ gcd (n, \ phi (n))} \ equiv 1 \ pmod {n} [/ math]. Usando el teorema fundamental de la aritmética, podemos denotar [matemáticas] n = p_1 ^ {a_1} p_2 ^ {a_2} \ cdots p_k ^ {a_k} [/ matemáticas], donde [matemáticas] p_j [/ matemáticas] es primo para [matemáticas] j = 1, 2, \ ldots, k [/ matemáticas]. Entonces, [matemáticas] \ phi (n) = p_1 ^ {a_1-1} (p_1 -1) p_2 ^ {a_2-1} (p_2 -1) \ cdots p_k ^ {a_k-1} (p_k -1) [ /matemáticas]. Sigue a [matemáticas] p_1 ^ {a_1-1} p_2 ^ {a_2-1} \ cdots p_k ^ {a_k-1} | \ gcd (n, \ phi (n)) [/ math]. Pero, no veo cómo demostrar que no siempre es válido o no de esta configuración.

Notas:

Si es válido, una forma de demostrarlo es mediante inducción en [math] k [/ math]. , lo que significa que puede probar el caso [math] n = p ^ k [/ math] para un entero primo y no negativo [math] k [/ math].

Si el reclamo no es válido, deberíamos usar computadoras para verificar si [math] 2 ^ n \ equiv 1 \ pmod {n} [/ math] en las computadoras. Siento que el reclamo puede no ser correcto.

Lo que puedo decirte es que si no es cierto, verificar en las computadoras para encontrar un contraejemplo podría ser una tarea muy grande o incluso imposible. ¡Más allá de eso, no tengo idea de inmediato! El reclamo no parece familiar; Quiero decir que no he visto tal afirmación en la teoría de números. Si no es un reclamo correcto, refutarlo podría ser mucho más difícil que probarlo. Por lo tanto, debería dejar de fumar al menos por ahora.