Calcular $121^{199} \mod 300$

Question

Utilizando el pequeño teorema de Fermat demostré que

$$121^{199} = 121^{39} \mod 300$$

(como $\phi(300)$ es $80$ ) pero no creo que pueda dejarlo así. Mi pregunta es cómo puedo resolver $121^{39}\hspace{-3mm}\mod 300$ . ¿Alguna idea o sugerencia?

Answer 1

Probablemente no sea mejor que el método de Jyrki, pero lo expongo de todos modos. En primer lugar, has pasado por alto que estás tratando con un número cuadrado. Así que

$$121^{39}\equiv11^{78}\equiv11^{-2}\pmod{300}$$

$11$ tiene una prueba de divisibilidad bastante fácil, por lo que no es tan difícil encontrar un múltiplo de $11\equiv1\pmod{300}$ . A $3$ -no funcionará como la suma del primer dígito y el $1$ no puede ser un múltiplo de $11$ . En $4$ -números de dígitos que empiezan por $1$ el único múltiplo de $11$ es $1001$ que no funciona. Para un primer dígito de $2$ Por otro lado, tenemos $2101$ ( $2-1+0-1=0$ ).

$$\frac{2101}{11}=191\equiv-109\pmod{300}$$

Ahora que tenemos la inversa de $11$ Sólo tenemos que cuadrarlo.

$$(-109)^2=10000+1800+81=11881=11700+181$$

Answer 2

El teorema chino del resto es tu amigo:

• Calcular el resultado en módulo $100$ (el orden de $121$ modulo $100$ es un número entero de un solo dígito)
• Calcular el resultado en módulo $3$ .
• Esto es suficiente para saber la respuesta modulo $3\cdot100$ como $\gcd(3,100)=1.$

---

[Edición 2702] Otros han dado soluciones basadas en la función totiente de Euler. Aunque a menudo es una herramienta indispensable para atacar problemas como éste, creo que hay que estirar las limitaciones de las herramientas elementales. A pesar de que tales soluciones son un poco ad hoc. Es muy útil disponer de conceptos procedentes de la teoría elemental de grupos, y constituyen una forma de destilar lo que hemos aprendido a lo largo de los siglos. Pero para la mente matemática en desarrollo, una aventura de experimentación tiene sus méritos. Recuerdo haber resuelto restos como éste en la escuela sin ningún concepto más profundo, algunos de los cuales uno sólo aprende a apreciar más tarde. Lo que sigue es el resultado de esa experimentación. Por supuesto, mezclado con la retrospectiva de haber aprendido sobre la TRC y demás.

Módulo $100$ tenemos $121\equiv21$ . El atajo clave aquí proviene de la observación trivial de que $10^2=100\equiv0$ . Por lo tanto, todos los términos, excepto la constante y los términos lineales, desaparecen en el módulo $100$ cuando aplicamos el teorema del binomio $$ \begin{aligned} 21^n&=(1+20)^n=1+\binom{n}1 20+\binom{n}2 20^2+\cdots\\ &\equiv 1+20\cdot n\pmod{100}. \end{aligned} $$ Por lo tanto, $$21^{199}\equiv1+199\cdot20\equiv81\pmod {100}.$$ Módulo $3$ las cosas son triviales. $121\equiv1\pmod3$ Así que $121^{199}\equiv1\pmod3$ también.

El módulo anterior $100$ nos dice que el resto modulo $300$ es $81$ , $181$ o $281$ . De ellos, sólo $181$ es congruente con $1$ modulo $3$ Así que esa es la respuesta.

Polonio: "Aunque esto sea una locura, hay método en ello".

Answer 3

Pensándolo bien, quizá lo mejor sea una combinación de los 2 métodos anteriores. De nuevo

$$121^{39}\equiv11^{78}\equiv11^{-2}\equiv121^{-1}\pmod{300}$$

Y ahora utiliza el teorema chino del resto para encontrar la inversa de $121$ . Tenemos

$$121\equiv-4\pmod{25}\text{ and }121\equiv1\pmod{12}$$

Así que nuestra inversa es equivalente a $6\pmod{25}$ y $1\pmod{12}$ .

Answer 4

Hay varios enfoques para este cálculo.

---

Fuerza bruta inteligente

Escriba $199=11000111_{\text{two}}$ luego trabajar mod $300$ con exponentes binarios: $$ \begin{align} 1&\equiv121^0\\ 121&\equiv121^1&&\text{multiply by }121\\ 241&\equiv121^{10}&&\text{square}\\ 61&\equiv121^{11}&&\text{multiply by }121\\ 121&\equiv121^{110}&&\text{square}\\ 241&\equiv121^{1100}&&\text{square}\\ 181&\equiv121^{11000}&&\text{square}\\ 61&\equiv121^{110000}&&\text{square}\\ 181&\equiv121^{110001}&&\text{multiply by }121\\ 61&\equiv121^{1100010}&&\text{square}\\ 181&\equiv121^{1100011}&&\text{multiply by }121\\ 61&\equiv121^{11000110}&&\text{square}\\ 181&\equiv121^{11000111}&&\text{multiply by }121\\ \end{align} $$ Por lo tanto, $$ 121^{199}\equiv181\pmod{300} $$ Como señala Bill Dubuque en los comentarios, esto se conoce como exponenciación al cuadrado .

---

Teorema Chino del Resto y Pequeño Teorema de Fermat

Tenga en cuenta que $300=3\cdot4\cdot25$ . Además, $121\equiv1\pmod3$ y $121\equiv1\pmod4$ Por lo tanto, $$ 121^{199}\equiv1\pmod{12}\tag{1} $$ Ahora sólo tenemos que trabajar mod $25$ .

$121\equiv-4\pmod{25}$ y $199\equiv-1\pmod{20}$ donde $20=\phi(25)$ . Por lo tanto, $$ \begin{align} 121^{199} &\equiv(-4)^{-1}\\ &\equiv6\qquad\pmod{25}\tag{2} \end{align} $$ Podríamos haber utilizado el Algoritmo Euclidiano Extendido para obtener $(-4)^{-1}\equiv6\pmod{25}$ pero parecía tan evidente.

Tenemos que encontrar un $x$ que satisface $$ \begin{align} x&\equiv1\pmod{12}\\ x&\equiv6\pmod{25} \end{align}\tag{3} $$ Podemos resolver $(3)$ resolviendo $$ \begin{align} x&\equiv1\pmod{12}\\ x&\equiv0\pmod{25} \end{align}\tag{4} $$ y $$ \begin{align} x&\equiv0\pmod{12}\\ x&\equiv1\pmod{25} \end{align}\tag{5} $$ y añadiendo $1\times$ la solución a $(4)$ a $6\times$ la solución a $(5)$ .

De nuevo, podríamos utilizar el Algoritmo Euclidiano Extendido para resolver $(4)$ y $(5)$ pero cada uno tiene una solución aparentemente evidente. $(4)$ tiene una solución de $x=25$ y $(5)$ tiene una solución de $x=-24$ .

Así, como se ha afirmado anteriormente, obtenemos una solución para $(3)$ con $$ x=1\times25+6\times(-24)=-119\equiv181\pmod{300}\tag{6} $$

Answer 5

${\rm mod}\ 25\!:\ \overbrace{11^{20}\equiv 1}^{\large\rm Euler\ \varphi}\,\Rightarrow\, x = 11^{398}\equiv \dfrac{1}{11^2}\equiv \dfrac{-24}{-4}\equiv \color{}6\iff x = \color{#0a0}{6\!+\!25n}$

${\rm mod}\ 12\!:\ 11^{398}\equiv (-1)^{398}\equiv \underbrace{1\equiv \color{#0a0}{6\!+\!25n}\equiv 6\!+\!n}_{\Large n\ \equiv\ -5\ \equiv\ \color{#c00}7}\ \Rightarrow\ x = 6\!+\!25(\underbrace{\color{#c00}7\!+\!12k}_{\Large n}) = 181+300k$