Números primos para poder 100

Question

Hice las siguientes observaciones:

$$ p^{100} \equiv 1 \pmod {1000}$$

$p$ es un número primo diferente $2$ y $5$

Comprobado lo anterior hasta el $p = 127$ y, para saber el motivo y si es cierto para todos números primos salvo el 2 y 5, y si ¿cuál es su prueba?

Answer 1

Usted puede encontrar esta relación capturado en el Carmichael función de $\lambda(1000)=100$, que representa la mayor exponencial ciclo de cualquier número de $\bmod 1000$. Para los números de $a$ coprime a $1000$, esto asegura que el $a^{100}\equiv 1 \bmod 1000$, ya que los ciclos más cortos de lo $100$, sin embargo, se dividen $100$.

Esto varía de la de Euler totient función de $\phi(1000) = 400$ por dos razones; los poderes de $2$ son tratados de forma ligeramente diferente y los resultados de las distintas primer poderes (aquí $2^3$$5^3$) son combinados por el mínimo común múltiplo, no por la multiplicación.

Answer 2

Comience por hacer una lista de la primera $p - 1$ positivos múltiplos de $a$:

$$a, 2a, 3a, \ldots, (p - 1)a$$

Supongamos que $ra$ $sa$ son el mismo modulo $p$, luego tenemos a $r \equiv s \pmod p$, por lo que el $p - 1$ múltiplos de arriba son distintas y distinto de cero; es decir, deben ser congruentes a $1, 2, 3, \ldots, p - 1$ en un cierto orden.

Multiplicar todas estas congruencias juntos y nos encontramos con $$a \cdot 2a \cdot 3a \cdot \ldots \cdot (p - 1)a = 1 \cdot 2 \cdot 3 \cdot \ldots \cdot (p - 1) \pmod p$$ o mejor, $a(p - 1)(p - 1)! \equiv (p - 1)! \pmod p$. Dividir ambos lados por $(p - 1)!$ para completar la prueba.

A veces Fermat poco teorema se presenta en el siguiente formulario:

Corolario. Deje $p$ ser una de las primeras y $a$ cualquier entero,$ap \equiv a \pmod p$. Prueba. El resultado es trivial (ambos lados son iguales a cero) si $p$ divide $a$. Si $p$ no divide $a$, entonces sólo tenemos que multiplicar la congruencia en Ese pequeño teorema de por $a$ para completar la prueba.

Answer 3

Estados del teorema de EULERs

$p^{\phi(1000)}=p^{400} \equiv 1 \mod 1000$

Podemos conseguir que más señalando $p^{\phi 8} = p^4 \equiv 1 \mod 8$ y así $p^{100} \equiv 1^{25} = 1 \mod 8$. Asimismo $p^{\phi 125} = p^{100}\equiv 1 \mod 125$.

Así $p^{100} \equiv k*125+1 \mod (125*8=1000)$ $k = 0...7$ y $p^{100} \equiv j*8 + 1 \mod (8*125=1000)$ $j = 0..... 124$.

$8j = 125k$ $k=0...7$y $j= 0...124$ medios $k = 0$ y $j=0$ y $p^{100} \equiv 1 \mod 1000$.

===

$\phi(p^n) = (p-1)(p^{n-1})$ % primer $p$lo $\phi(8) = 4$ y $\phi(125) = 100$. $\phi(mn) = \phi(m)\phi(n)$ Si $\gcd(m,n) = 1$ % que $\phi(1000) = 400$, BTW.

También si $a \equiv b \mod n \implies a = b + kn$ $k$. Que $k = j + lm$ $0 \le j \le m$ y $a = b + jn + lmn$ lo $a \equiv b + jn \mod mn$ $j = 0....(m-1)$.