¿Para qué valor de n es [matemática] (101) ^ n – 1 [/ matemática] divisible por [matemática] (100) ^ 3 [/ matemática]?

Answer 1

Para todos los n de la forma 10000k

Considere [math] N = p ^ aq + 1 [/ math] donde p es primo, a> 0 yq es un número entero que no divide p. ¿Cuál es el número natural más pequeño r tal que [matemática] N ^ r \ equiv 1 \ pmod {p ^ {a + 1}} [/ matemática]?

Expandir usando el teorema binomial:
[matemáticas] (p ^ aq + 1) ^ r = p ^ {ar} q ^ r + rp ^ {a (r-1)} q ^ {r-1}… rp ^ aq + 1 [/ matemáticas]
Ahora, como [matemáticas] a> 0, ak \ ge a + 1 \, \ forall k> 1 [/ matemáticas]
Por lo tanto, todos los términos en la expansión, excepto los dos últimos, son divisibles por [math] p ^ {a + 1} [/ math]. Como resultado,
[matemáticas] N ^ r \ equiv rp ^ aq + 1 \ pmod {p ^ {a + 1}} [/ matemáticas]. Para que esta cantidad sea [matemática] 1 \ pmod {p ^ {a + 1}} [/ matemática], requerimos que r sea un múltiplo de p.

Por inducción, se puede demostrar que [math] N ^ r \ equiv 1 \ pmod {p ^ {a + l}} [/ math] iff r es un múltiplo de [math] p ^ l [/ math].

Podemos usar este resultado para resolver el problema. Queremos [matemáticas] (2 ^ 2 5 ^ 2 + 1) ^ n
\ equiv 1 \ pmod {2 ^ {2 + 4}} [/ math] y [math] (2 ^ 2 5 ^ 2 + 1) ^ n
\ equiv 1 \ pmod {5 ^ {2 + 4}} [/ math]. Por lo tanto, obtenemos que n debería ser un múltiplo de 2 ^ 4 y 5 ^ 4. Combinando, n debería ser un múltiplo de 10000.

En general, [matemática] 101 ^ n-1 [/ matemática] es divisible por [matemática] 100 ^ k [/ matemática] si n es un múltiplo de [matemática] 100 ^ {k-1} [/ matemática]

Answer 2

El teorema de Euler establece que si n y a son números enteros positivos primos, entonces

[matemáticas] a ^ {\ phi (n)} \ equiv 1 \ mod n [/ matemáticas]

Donde [math] \ phi (n) [/ math] es la función de Euler Totient. En pocas palabras, es el número de todos los enteros menores que n que son primos co-primos.

El total de [matemáticas] 100 ^ k [/ matemáticas] es [matemáticas] 4 \ por 10 ^ {2k-1} [/ matemáticas]. Como 101 y [math] 100 ^ k [/ math] siempre son primos, [math] 101 ^ n – 1 [/ math] es divisible por [math] 100 ^ k [/ math] cuando n es un múltiplo de [matemáticas] 4 \ por 10 ^ {2k-1} [/ matemáticas].