Manera fácil de calcular $k^{20}=1\pmod{101}$?

Question

Sé que se supone duro para calcular el opuesto de ($20^k$), básicamente, el discreto registro de problema. También sé que es fácil de comprobar para algunos $k$ si $k^{20}=1\pmod{101}$ mantiene. Las soluciones son 1, 6, 10, 14, 17, ... sin Embargo, hay una manera fácil de calcular directamente estos valores para decir $1 < k < 100$?

Answer 1

Bien, $101$ es un número primo, por lo que el grupo $\mathbb{Z}_{101}^*$ es cíclico de orden $100$. Por lo tanto, nada coprime a $101$ elevado a $100$ le da algo congruente a $1$ modulo $101$ (también conocida como la Pequeña de Fermat). Por lo tanto $$k=a^5$$ es una solución de la congruencia $k^{20}\equiv1\pmod{101}$ para todos los enteros $a$ coprime a $101$. Prueba: $$k^{20}=(a^5)^{20}=a^{100}\equiv1\pmod{101}.$$ Por lo $a=1$ da $k=1$, $a=2$ da $k=32$, $a=3$ da $k=243=41$ et cetera.

Se desprende también de las propiedades básicas de los grupos cíclicos que usted obtiene todas las soluciones de (hasta congruencia) de esta manera.

---

Además (en respuesta a un útil intercambio de comentarios con N. S. y TonyK): Sabemos que hay exactamente 20 no congruentes soluciones. Además, las soluciones forman un subgrupo. Vamos a ver el fin de la primera solución de $k=32$ hemos encontrado con $a=2$. Tenemos $k^2=1024=14$, $k^4=196=-6$, por lo $k^5=-192=10$. Esto implica que $k^{10}=100=-1$. Por lo tanto, $k=32$ no puede ser de orden, que es un factor de $4$ o $10$, por lo que su fin es $20$ y hemos terminado. Si que había llegado a menos de 20 soluciones con esto $k$ le gustaría probar con otro valor de $a$ y comprueba si que ayuda. Este algoritmo termina al menos tan rápido como sistemáticamente la búsqueda de una raíz primitiva.

Answer 2

De encontrar una raíz primitiva: Por ensayo y error, encontrará por ejemplo,$6$. A continuación, los poderes de la $6$ son también raíces. Por desgracia, que le da a sólo diez soluciones, por lo que nos hemos perdido algunas soluciones. Encontramos otra solución, por ejemplo,$10$, ya sea por ensayo y error o por reconocer que la $101=10^2+1$. Luego multiplicando el que anteriormente se encuentran diez soluciones por $10$ da el restante diez raíces.