¿Por qué [matemáticas] \ frac {2 ^ {\ ell k} – 1} {2 ^ \ ell – 1} \ equiv 2 ^ {\ ell k – 1} (2 ^ \ ell – 1) ^ {p-2 } \ pmod {p} [/ math] cuando p = 100000007?

El grupo multiplicativo de enteros (mod p) es un grupo de orden p – 1 , por lo que cualquier elemento distinto de cero del grupo a la potencia (p – 1) -st es la identidad. (Esta es la declaración conocida como el pequeño teorema de Fermat).

Suponga que [matemáticas] 2 ^ \ ell – 1 [/ matemáticas] no es divisible por p. Entonces tenemos

[matemáticas] (2 ^ \ ell – 1) ^ {p-1} \ equiv 1 \ pmod {p} [/ matemáticas]

Multiplicando ambos lados por [matemáticas] 2 ^ {\ ell k} – 1 [/ matemáticas], tenemos

[matemáticas] (2 ^ {\ ell k} – 1) (2 ^ \ ell – 1) ^ {p-1} \ equiv (2 ^ {\ ell k} – 1) \ pmod {p} [/ matemáticas]

Dividiendo a través de [matemáticas] 2 ^ \ ell – 1 [/ matemáticas], obtenemos

[matemáticas] (2 ^ {\ ell k} – 1) (2 ^ \ ell – 1) ^ {p-2} \ equiv \ frac {(2 ^ {\ ell k} – 1)} {2 ^ \ ell – 1} \ pmod {p} [/ matemáticas]

Me imagino que el caso donde [math] 2 ^ \ ell – 1 [/ math] es divisible por p no es mucho más difícil, pero realmente no lo pensé. Alternativamente, podría usar el hecho de que

[matemáticas] \ frac {2 ^ {\ ell k} – 1} {2 ^ \ ell – 1} = 2 ^ {\ ell (k-1)} + 2 ^ {\ ell (k-2)} + \ cdots + 1 [/ math]