Prime numbers to power 100 I made the following observations:
$$ p^{100} \equiv 1 \pmod {1000}$$
$p$ is a prime number other than $2$ and, $5$
I checked the above till $p = 127$ and, want to know the reason for it and whether it is true for all prime numbers except 2 and 5 and if so, what is its proof?
 A: You can find this relationship captured in the Carmichael function $\lambda(1000)=100$, representing the largest exponential cycle of any number $\bmod 1000$. For numbers $a$ coprime to $1000$, this ensures that $a^{100}\equiv 1 \bmod 1000$, since cycles shorter than $100$ will nevertheless divide $100$.
This varies from the Euler totient function $\phi(1000) = 400$ for two reasons; powers of $2$ are treated slightly differently and results from distinct prime powers (here $2^3$ and $5^3$) are combined by least common multiple, not by multiplication.
A: Start by listing the first $p - 1$ positive multiples of $a$:
$$a, 2a, 3a, \ldots, (p - 1)a$$
Suppose that $ra$ and $sa$ are the same modulo $p$, then we have $r \equiv s \pmod p$, so the $p - 1$ multiples of a above are distinct and nonzero; that is, they must be congruent to $1, 2, 3, \ldots, p - 1$ in some order. 
Multiply all these congruences together and we find
$$a \cdot 2a \cdot 3a \cdot \ldots \cdot (p - 1)a = 1 \cdot 2 \cdot 3 \cdot \ldots \cdot (p - 1) \pmod p$$
or better, $a(p - 1)(p - 1)! \equiv (p - 1)! \pmod p$. Divide both sides by $(p - 1)!$ to complete the proof.
Sometimes Fermat's little theorem is presented in the following form:

Corollary. Let $p$ be a prime and $a$ any integer, then $ap \equiv a \pmod p$.
  Proof. The result is trival (both sides are zero) if $p$ divides $a$. If $p$ does not divide $a$, then we need only multiply the congruence in Fermat's little theorem by $a$ to complete the proof.

A: Eulers theorem states
$p^{\phi(1000)}=p^{400} \equiv 1 \mod 1000$
We can get that tighter by noting $p^{\phi 8} = p^4 \equiv 1 \mod 8$  and so $p^{100} \equiv 1^{25} = 1 \mod 8$.  Likewise $p^{\phi 125} = p^{100}\equiv 1 \mod 125$.
So $p^{100} \equiv k*125+1 \mod (125*8=1000)$ for $k = 0...7$ and $p^{100} \equiv j*8 + 1 \mod (8*125=1000)$ for $j = 0..... 124$.
$8j = 125k$  with $k=0...7$ and $j= 0...124$ means $k = 0$ and  $j=0$ and $p^{100} \equiv 1 \mod 1000$.
===
$\phi(p^n) = (p-1)(p^{n-1})$ for prime $p$ so $\phi(8) = 4$ and $\phi(125) = 100$.  $\phi(mn) = \phi(m)\phi(n)$ if $\gcd(m,n) = 1$ so $\phi(1000) = 400$, BTW.
Also if $a \equiv b \mod n \implies a = b + kn$ for some $k$.  Let $k = j + lm$ for $0 \le j \le m$ then $a = b + jn + lmn$ so $a \equiv b + jn \mod mn$ for some $j = 0....(m-1)$.
