módulo de teoría de números

Question

Encontrar todas las soluciones de x ^ 11 ≡ 1 (mod 23). Justificar su trabajo

Si intento aplicar el poder de 11 a todos los valores del 1 al 23, obtengo un valor demasiado grande para luego poder ver si pueden reducirse modulo 23.

¿Hay una manera más simple? cualquier ayuda sería apreciada

Answer 1

Cuando se hace la aritmética modular que no necesita ocuparse de números realmente grandes porque se reduce en el camino. Así $2^{11} \pmod{23}$ calcula $$\begin{align} 2^2 & = 4\ 2^3 & = 8\ 2^4 & = 16\ 2^5 & = 32 \equiv 9\ 2^6 & \equiv 2 \times 9 = 18\ 2^7 & \equiv 2 \times 18 = 36 \equiv 13 \end {Alinee el} $ y así sucesivamente.

Hay otros atajos que ayudan con ese problema, pero el principio general (no necesita números grandes) es necesario recordar todo el tiempo.

Answer 2

Por criterio de Euler, la solución es exactamente el distinto de cero plazas mod $23$.

Así calcular $1^2, 2^2, \dots, 11^2 \bmod 23$.

Answer 3

Exponenciación al cuadrado es muy adecuado para este tipo de cálculos (donde sea necesario) en la aritmética modular. Como un ejemplo de cómo esto puede ser usado en este caso:

$$\begin{align} 13^2 &= 169 \equiv 8 \bmod 23\\ 13^4 &\equiv 8^2 \equiv 18 \bmod 23\\ 13^8 &\equiv 18^2 \equiv (-5)^2 \equiv 25\equiv 2 \bmod 23\\ \text {and then}\qquad\\ 13^{11} = 13^8\cdot13^2\cdot13^1 &\equiv 2\cdot8\cdot 13 \equiv 208 \equiv 1\bmod 23\\ \end{align}$$

En este caso, dado que el $a^{22}\equiv 1 \bmod 23$ cualquier $a$ coprime a $23$ por Fermat poco teorema, sólo tenemos que encontrar a todos los $b$ tal que $b\equiv a^2\bmod 23$ algunos $a$. En lugar del cálculo anterior, nos encontramos con $6^2=36\equiv 13 \bmod 23$, por lo que, necesariamente,$13^{11}\equiv 6^{22}\equiv 1 \bmod 23$.