Cómo Comprar Evalúe

Question

Nota: $5379 = 3 \times 11 \times 163$.

He probado pequeño teorema Teorema chino del resto y de Fermat, consiguió en cuanto: $$ 1234 ^ {1234} = 1 \pmod{3} \\ 1234 ^ {1234} = 5 \pmod{11} $$ con un poco más trabajo: $$1234^{1234} = 93^{100} \pmod{163}$ $

¿Pero realmente no ayuda $93^{100}$?

¿WolframAlpha me dice que el $\phi(5379)=3240>1234$ así que no puedo usar el teorema de Euler?

Nota: esto apareció en una hoja de problema pregrado 1er año. Así que probablemente, no demasiada tecnología es necesaria.

Answer 1

Noodling un poco produce las siguientes, donde todos congruencias son mod $163$:

$$93\equiv256=2^8\implies2^{10}\cdot93^{100}\equiv2^{810}=2^{162\cdot5}\equiv1$$

Teniendo en cuenta que $2^{10}=1024\equiv46$, es calcular $46^{-1}$mod $163$. Esto podría hacerse mediante un sencillo Algoritmo euclidiano, pero me pareció bastante fácil argumentar como sigue:

$$\begin{align} 23\cdot7=161\equiv-2 &\implies46\cdot7\equiv-4\\ &\implies46\cdot7\cdot(-41)\equiv164\equiv1\\ &\implies46^{-1}\equiv-287\equiv39 \end {Alinee el} $$

Con todo, tenemos

$$93^{100}\equiv39\mod163$$

Nota: El uno cómputo que tenía apagado al lado fue

$$1024-6\cdot163=1024-978=46$$

Todo lo que podía hacer fácilmente en mi cabeza.

Answer 2

Bien esto está lejos de ser perfecto, pero funciona si tienes suficiente tiempo o una calculadora. $$93\equiv -70\pmod{163}$$

$$\begin{align} 93^{100}&\equiv(-70)^{100}\\ &= 490^{50}\cdot10^{50}\\ &\equiv 10^{50}\\ &= 2^{50}\cdot 5^{50}\\ &= 1024^5\cdot 3125^{10}\\ &\equiv 46^5\cdot 28^{10}\\ &=2^{25}\cdot 23^5\cdot 7^{10}\\ &= 2^{25}\cdot (23\cdot 7)^5\cdot 7^5\\ &= 2^{25}\cdot (161)^5\cdot 7^5\\ &\equiv 2^{10}\cdot2^{10}\cdot 2^5\cdot (-2)^5\cdot 7^5\\ &=1024\cdot 1024\cdot (-1024)\cdot 7^5\\ &\equiv -46^3\cdot 7^5\\ &= -(46\cdot 7)^3\cdot 7^2\\ &= -(322)^3\cdot 7^2\\ &\equiv -(-4)^3\cdot 49\\ &= 49\cdot 64\\ &\equiv 39 \end {Alinee el} $$

Answer 3

$93^{100}$ puede ser calculada con el Rápido algoritmo de Exponenciación. Primera nota:$93^2\equiv 10\mod163$. Por lo tanto, todos tenemos que calcular es $10^{50}\mod 163$

Se puede hacer con una calculadora de mano. La primera nota que el exponente en base $2$ escrito $110010$, y usamos estos dígitos (de derecha a izquierda) en el algoritmo: en cada paso, el número de $a=10$ se eleva al cuadrado y la reducción de modulo $163$. El poder $p$ es inicialmente igual a $1$ y, si el dígito en el paso es $1$, se multiplica el anterior valor de $p$ por el valor actual de $a$ y reducir el modulo $163$: $$\begin{array}{c|cr|cr} \text{exponent}&a&&p\\ \hline 0&a&10&1&1\\ 1 & x^2 & 100 & x^2&100\\ 0 & x^4 & 57& x^2&100\\ 0 & x^8 & -11& x^2&100\\ 1 & x^{16} & -42& x^{18}&38\\ 1 & x^{32} &-29& x^{50}& 39\\ \end{array}$$

Queda por resolver el sistema de congruencias: $$\begin{cases} x\equiv 1\mod 3\\x\equiv 5\mod 11\\x\equiv39\mod163 \end{casos}$$

Como $4\times 3-11=1$, la solución de los dos primeros congruencias es $x\equiv5\cdot 4\cdot3-1\cdot 11=49\equiv16\mod33$.

Además, una de Bézout la relación entre el $163$ $33$ es, por el algoritmo de Euclides Extendido, $16\cdot163-79\cdot33=1$, de ahí la solución del sistema de congruencias $$\begin{cases} x\equiv 16\mod 33\\x\equiv39\mod163 \end{casos}\iff x\equiv 16^2\cdot163-39\cdot79\cdot33\equiv4603\mod5379.$$