# Prime numbers to power 100

$$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?

• Do you know Fermat's Little Theorem? – fleablood Mar 13 '17 at 16:50
• Hint: $p^{100}\equiv 1\pmod{8}$ and $p^{100}\equiv 1\pmod{125}$. – Thomas Andrews Mar 13 '17 at 16:51
• It's actually true for any $a$ relatively prime to $10$: $a^{100}\equiv 1\pmod{1000}$. – Thomas Andrews Mar 13 '17 at 16:52
• @thomasandrews Could you please write an answer to it explaining all the facts. Thank You – Mrigank Shekhar Pathak Mar 13 '17 at 16:57
• @G.Sassatelli $\phi(1000) = 400$, so Euler's theorem does a poor job of estimating the exponent of $\mathbb Z_{1000}$. Maybe Euler's theorem + CRT would be a better hint? – Erick Wong Mar 15 '17 at 2:01

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.

• Also for any $a$, $a^{103}\equiv a^{3} \bmod 1000$, because $3$ is the largest exponent in the prime decomposition of $1000$, So $2^{103} \equiv 8 \bmod 1000$ even though $2^{100} \not\equiv 1 \bmod 1000$. – Joffan Mar 13 '17 at 17:29

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)$.

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.

• Does this answer look the way you meant it to look in the Web interface? The help pages have advice on how to format posts correctly. – David K Mar 13 '17 at 17:23
• Check meta.math.stackexchange.com/questions/5020/… for help in formula formatting. – Joffan Mar 13 '17 at 17:30
• At least for the new ones it wouldn't kill us to help them out a little. – Robert Soupe Mar 14 '17 at 18:55