¿Cómo se puede calcular el módulo de un número realmente elevado con una gran potencia, con un muy alto mod número?

Question

Necesito trabajar $516489222^{22} \pmod{96899}$. Sé que hay formas más fáciles de trabajar en esto, pero soy realmente luchando.

Answer 1

Tenga en cuenta que $516489222 \equiv 17552 \pmod{96899}$. Esto le da

$$516489222^{22} \equiv 17552^{22} \pmod{96899}.$$

Ahora es fácil calcular

$$\begin{align*} 17552^{2^{1}} &\equiv 30783 \pmod{96899}\\ 17552^{2^{2}} &\equiv 30783^{2} \equiv 17768 \pmod{96899}\\ 17552^{2^{3}} &\equiv 17768^{2} \equiv 4882 \pmod{96899}\\ 17552^{2^{4}} &\equiv 4882 ^{2} \equiv 93669 \pmod{96899}. \end{align*}$$

Desde $22 = 2^{4} + 2^{2} + 2^{1},$ se sigue que

$$\begin{align*} 17552^{22} &\equiv 17552^{2^{4}} \cdot 17552^{2^{2}} \cdot 17552^{2^{1}} \pmod{96899} \\ &\equiv 93669 \cdot 17768 \cdot 30783 \pmod{96899} \\ &\equiv 4647 \pmod{96899} \end{align*}$$

Answer 2

He aquí un poco de la descripción de alto nivel de los varios trucos que se pueden usar para hacer números más pequeños y cálculos "más fácil". Puede que tenga algunos conocimientos elementales de la teoría de números para entender estos trucos.

Las cosas pueden ser más fáciles por primera factorización $96899 = 11 \cdot 23 \cdot 383$. A continuación, para encontrar $$516489222^{22} \pmod{96899},$$ es suficiente para encontrar $$\begin{align} &516489222^{22} \pmod{11}, \tag{1.} \\ &516489222^{22} \pmod{23}, \tag{2.} \\ &516489222^{22} \pmod{383}, \tag{3.} \end{align}$$ y luego combinar los resultados utilizando el Teorema del Resto Chino. Para cada uno de estos tres casos, vamos a utilizar el hecho de que para todas las $a \not\equiv 0 \pmod{m}$, tenemos $$a^b \equiv (a \mod m)^{(b \mod \phi(m))} \pmod m,$$ para reducir los números en los cálculos considerablemente. Aquí $\phi$ es de Euler totient función, y ser capaz de reducir los exponentes con los múltiplos de $\phi(m)$ es una consecuencia de el teorema de Euler. (En nuestras aplicaciones $m$ es siempre el primer, en cuyo caso el teorema es también conocido como Fermat poco teorema, donde $\phi(p) = p-1$.)

1. Para la primera, el uso de ese $516489222 \equiv -4 \pmod{11}$$22 \equiv 2 \pmod{\phi(11)}$, tenemos $$516489222^{22} \equiv (-4)^2 \equiv 16 \equiv 5 \pmod{11}.$$
2. Para el segundo, el uso de ese $516489222 \equiv 3 \ [\not\equiv 0] \pmod{23}$$22 \equiv 0 \pmod{\phi(23)}$, obtenemos $$516489222^{22} \equiv 3^0 \equiv 1 \pmod{23}.$$
3. Por último, el uso de ese $516489222 \equiv -66 \pmod{383}$, obtenemos $$516489222^{22} \equiv (-66)^{22} \pmod{383}.$$ No conseguimos haciendo algunos cómputos modulares aquí, pero el trabajo se puede reducir un poco por el uso de la plaza y se multiplican: $$516489222^{22} \equiv (-66)^{22} \equiv ((-66)^2)^{11} \equiv 143^{11} \equiv 143 \cdot (143^2)^5 \equiv 143 \cdot 150^5 \\ \equiv 143 \cdot 150 \cdot (150^2)^2 \equiv 2 \cdot (-97)^2 \equiv 2 \cdot 217 \equiv 51 \pmod{383}.$$

Para concluir, hemos $$516489222^{22} \equiv \begin{cases} 5 \pmod{11} \\ 1 \pmod{23} \\ 51 \pmod{383} \end{cases}$$ La combinación de ellos, el uso de la CRT, obtenemos $$516489222^{22} \equiv 4647 \pmod{11 \cdot 23 \cdot 383 = 96899}$$

Answer 3

La propiedad útil es $$(x\mod{n})(y\mod{n})\equiv(xy \mod{n})$$ If you iterate this, it works for integer powers too. That means that the OP is equal to $$(616489222 \mod{96899})^{22}\pmod{96899}\equiv 17552^{22}\pmod{96899}$$

Podemos utilizar la propiedad de nuevo, observando que $(x^2)^{11}\pmod{n}\equiv (x^2\mod{n})^{11}\pmod{n}$. Por lo tanto $$17522^{22}\pmod{96899}\equiv (17522^2\mod{96899})^{11}\pmod{96899}\equiv44452^{11}\pmod{96899}$$

Unos pocos pasos más como este y te vas a hacer. Este proceso puede ser realizado más rápido mediante el uso de Wolfram Alpha, que puede manejar difícil de manejar, aritmética, incluyendo la OP en un solo paso.

Answer 4

El Teorema del Resto Chino puede ser útil en esta situación. Desde $96899=11*23*383$ basta calcular el número de $\pmod{11}, \pmod{23}$$\pmod{383}$.

$516489222 \equiv 7 \pmod{11}$. Por Fermat Poco Teorema De

$$(516489222)^{22} \equiv ((516489222)^{10})^27^2 \equiv 1 \cdot 7^2 \equiv 5 \pmod {11}$$

$516489222 \equiv 3 \pmod{23}$. Por Fermat Poco Teorema De

$$(516489222)^{22} \equiv 1 \pmod {23}$$

$516489222 \equiv 317 \equiv -66 \pmod{383}$. Entonces

$$(516489222)^{22} \equiv (-66)^{22} \equiv (143)^{11} \pmod {383}$$

Ahora

$$(143)^{2} \equiv 150 \pmod {383}$$ $$(143)^{4} \equiv 150^2 \equiv -97 \pmod {383}$$ $$(143)^{8} \equiv (-97)^2 \equiv 217 \pmod {383}$$ $$(143)^{11} \equiv (143)^{8} (143)^{2} 143 \equiv 217 \cdot 150 \cdot 143 \equiv -5 \cdot 143 \equiv 51 \pmod {383}$$

Ahora, usted puede utilizar el Teorema del Resto Chino para encontrar la única clase de $\pmod{96899}$ $7 \pmod{11}, 1 \pmod{23}$ $51 \pmod{383}$