7
$\begingroup$

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?

$\endgroup$
  • 1
    $\begingroup$ Do you know Fermat's Little Theorem? $\endgroup$ – fleablood Mar 13 '17 at 16:50
  • 1
    $\begingroup$ Hint: $p^{100}\equiv 1\pmod{8}$ and $p^{100}\equiv 1\pmod{125}$. $\endgroup$ – Thomas Andrews Mar 13 '17 at 16:51
  • $\begingroup$ It's actually true for any $a$ relatively prime to $10$: $a^{100}\equiv 1\pmod{1000}$. $\endgroup$ – Thomas Andrews Mar 13 '17 at 16:52
  • $\begingroup$ @thomasandrews Could you please write an answer to it explaining all the facts. Thank You $\endgroup$ – Mrigank Shekhar Pathak Mar 13 '17 at 16:57
  • $\begingroup$ @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? $\endgroup$ – Erick Wong Mar 15 '17 at 2:01
3
$\begingroup$

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.

| cite | improve this answer | |
$\endgroup$
  • $\begingroup$ 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$. $\endgroup$ – Joffan Mar 13 '17 at 17:29
1
$\begingroup$

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

| cite | improve this answer | |
$\endgroup$
1
$\begingroup$

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.

| cite | improve this answer | |
$\endgroup$
  • $\begingroup$ 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. $\endgroup$ – David K Mar 13 '17 at 17:23
  • $\begingroup$ Check meta.math.stackexchange.com/questions/5020/… for help in formula formatting. $\endgroup$ – Joffan Mar 13 '17 at 17:30
  • $\begingroup$ At least for the new ones it wouldn't kill us to help them out a little. $\endgroup$ – Robert Soupe Mar 14 '17 at 18:55

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.