Modulo Congruencia

Question

Cómo demostrar que $$7(100 ^{100}) + 8 \equiv 3^{90} - 21\ (\mathrm{mod} 28)?$$

---

Asumí que la afirmación era cierta. Luego pasé a demostrar que ambos lados tienen el mismo resto cuando se dividen por $28$ .

$7(100)(100^{99}) + 8$ da un resto de $8$ cuando se divide por $28$ .

No sé cómo obtener el mismo resto de $3^{90} - 21$ .

Answer 1

Usted sabe que $$3^3\equiv 97\equiv -1\pmod{28}.$$

Así que

$$3^{90}-21\equiv (-1)^{30}-21\equiv 8\pmod{28}.$$

Y puedes comprobar que $$100^4\equiv 100\pmod {28}$$

así que

$$7(100^{100})+8\equiv 7\times 100+8\equiv 8\pmod{28}.$$

Así que esta afirmación es cierta.

Answer 2

para calcular el resto de $3^{90}-21$ debes usar el teorema de eulers en el lado izquierdo, nota $\varphi(28)=12$ Así que $3^{90}=3^{84}3^6\equiv 3^6\equiv 27^2\equiv 1 \bmod 28$ Por lo tanto $3^{90}-21\equiv 1-21\equiv-20\equiv 8\bmod 28$

Answer 3

Como usted ha observado, $7\cdot 100^{100} \equiv 0 \bmod 28$ . Así que lo que queremos demostrar entonces es $3^{90}\equiv 8+21\equiv29\equiv 1 \bmod 28$

El Función de Carmichael $\lambda(28)={\rm lcm}(\lambda(4),\lambda(7)) = {\rm lcm}(2, 6) = 6$ significa que el ciclo de valores para $3^k \bmod 28$ es $6$ en longitud o divide $6$ de longitud, y como $\gcd(3,28)=1$ entonces sabemos $3^6\equiv 1 \bmod 28$ . De hecho, también podemos ver esto directamente ya que $3^3=27\equiv-1\bmod 28$ (pero este descubrimiento no es necesario).

Así que desde $3^6\equiv 1 \bmod 28$ entonces también $3^{90}\equiv (3^6)^{15}\equiv 1^{15}\equiv 1\bmod 28$ y el resultado se mantiene.