Demostrar que ${ ({ 3299 }^{ 5 }+6) }^{ 18 }\equiv 1\pmod{112}$

Question

¿Cómo lo resuelvo?

Demostrar que ${ ({ 3299 }^{ 5 }+6) }^{ 18 }\equiv 1\pmod{112}$

Además, sería muy útil que me dieras algo para leer sobre el tema ya que esto no se enseña en mi escuela y esta área de las matemáticas me parece interesante.

Answer 1

$$3299=51\pmod{112}=3\cdot17\pmod{112=\color{purple}{2^4\cdot7}}$$

Así que tenemos:

$$\color{red}{\text{modulo}\;\, 16\;\;\text{all the time}}:\;3299=3\cdot1=3\implies 3299^5=3^4\cdot3=1\cdot3=3\implies$$

$$(3299^5+6)^{18}=(3+6)^{18}=\left(9^2\right)^91^9=1$$

y ahora

$$\color{green}{\text{modulo}\;\;7\;\;\text{all the time}}: 3299=2\implies2^5=4\implies (3299^5+6)^{18}=$$

$$=(4-1)^{18}=3^{18}=(3^3)^6=(-1)^6=1$$

Así que ahí está.

Answer 2

Puedes aprovechar las siguientes propiedades de las congruencias:

Si $a \equiv b\ (\textrm{mod}\ m)$ y $c \equiv d\ (\textrm{mod}\ m)$ entonces:

$a+c \equiv b+d\ (\textrm{mod}\ m)$

$a^n \equiv b^n\ (\textrm{mod}\ m)$

y el hecho de que las congruencias son transitivas. Así, el paso 1 sería calcular el valor de $x$ :

$3299 \equiv x\ (\textrm{mod}\ 112)$

Una vez que haya calculado $x$ :

$3299^5 \equiv x^5\ (\textrm{mod}\ 112)$

y

$3299^5 + 6 \equiv x^5 + 6\ (\textrm{mod}\ 112)$

Entonces, si puedes demostrar que

$(x^5 + 6)^{18} \equiv 1\ (\textrm{mod}\ 112)$

la propiedad transitiva de las congruencias puede utilizarse para demostrar que

$3299^5 + 6 \equiv 1\ (\textrm{mod}\ 112)$

El problema de este enfoque es que $(x^5 + 6)^{18}$ es un número enorme. Pero, si utilizas la propiedad transitiva en ciertas partes del cálculo, puedes simplificar los cálculos. Por ejemplo, he calculado $x = 51$ en el primer paso. Como $51^5 + 6 \equiv 73 \ (\textrm{mod}\ 112)$ , se puede plantear $73$ a la $18$ de la potencia en lugar de $x^5 + 6$ . También tendría que romper el $73^{18}$ en múltiples cálculos también.

Cualquier libro de texto sobre teoría elemental de números sería un buen lugar para empezar a investigar esto. He estado leyendo un libro de texto escrito por Kenneth Rosen llamado "Elementary Number Theory and its applications".