$561 \mid 128^{561} - 128 \iff 2^{3920} \equiv 1 \pmod{561}$

Question

Comencé a aprender la teoría de los números, específicamente aritmética modular, y necesitan ayuda para entender el pasado de la equivalencia en el siguiente ejemplo :

$$561 \mid 128^{561} - 128 \iff 128^{561} \equiv128 \pmod{561} \iff (2^7)^{561} = 2^{3927} \equiv 2^7 \pmod{561}$$ $$\iff 2^{3920} \equiv 1 \pmod{561}.$$

Como ya he dicho, no entiendo la última equivalencia, específicamente ¿por qué somos capaces de "dividir" por $2^7$ (y por qué división está permitido si realmente se está dividiendo)?

Answer 1

Debido a $561$ es impar, es coprime a $2^7$, lo que significa que $2^7$ tiene un inverso multiplicativo modulo $561$, es decir, un número $x$ tal que $x\cdot 2^7 \equiv 1 \pmod{516}$. Usted no necesita saber que número es, simplemente que existe.

Ahora multiplique por $x$ a ambos lados de $2^{3927}\equiv 2^7 \pmod{561}$.

Answer 2

Tenemos $$ 561 \mid 128^{561} - 128 \iff 561 \mid 2^{3927} - 2^7 \iff 561 \mid 2^7(2^{3920} - 1) \iff 561 \mid 2^{3920} - 1 $$ La última equivalencia es un caso especial de

Si $\gcd(a,m) = 1$, $m$ divide $ab$ fib $m$ divide $b$.