4
$\begingroup$

I'm trying to understand intuitively why (p-1)th power of any integer(not divisible by p) leaves a remainder of 1 when divided by p. (where p is a prime number)

I understand that p times any integer becomes a multiple of p and would be divided p. Similarly, can I understand the growth of the exponential function and reason why p-1 th power of any integer is always congruent to 1 mod p.

$\endgroup$
7
  • 2
    $\begingroup$ Firstly, it's not any integer. It's only integers not divisible by $p$. Secondly, you might want to understand the variant of Fermat's little theorem which says that $a^p\equiv a\pmod p$ (which does work for all $a$. This one can be seen easily from the formula $(a+b)^p\equiv a^p+b^p\pmod p$, which follows from binomial expansion, and induction. $\endgroup$
    – Wojowu
    Sep 12, 2019 at 12:03
  • 2
    $\begingroup$ primes.utm.edu/notes/proofs/FermatsLittleTheorem.html $\endgroup$
    – user645636
    Sep 12, 2019 at 12:06
  • 1
    $\begingroup$ Seconding @Wojowu. Binomial theorem is your friend here. Show it for $a = 1$ then for the induction hypothesis assume it holds for $k$ then prove for $k+1$ with binomial theorem. There is a secondary result built into this that you need which is that $p$ divides $\binom{p}{m}$ for any $0< m < p$ where $p$ is prime. Primality is key here and it's used in a subtle way. $\endgroup$ Sep 12, 2019 at 12:06
  • 2
    $\begingroup$ you need nothing but the fact that the multiples of a are coprime to p as in the proof in my link. $\endgroup$
    – user645636
    Sep 12, 2019 at 12:09
  • 1
    $\begingroup$ @RoddyMacPhee That's a very nice way to do it. Definitely one of the cuter proofs I've seen for a simply-stated result. $\endgroup$ Sep 12, 2019 at 12:11

2 Answers 2

7
$\begingroup$

Your intuition to understand this result by analogy to a multiple of $p$ being divisible by $p$ will not work in this case. The standard explanation runs like this: For any number $a$ which is not divisible by $p$, we know that $a\equiv A \bmod p$ where $1\le A \le (p-1)$. Next, we look at the products $1\cdot A,\ 2\cdot A,\ 3\cdot A,\dots (p-1)\cdot A$. There are $(p-1)$ such products, and none of them have any factors of $p$.

We look at those products and ask if any two of them can have the same value $\bmod p$. The answer is no, because if they did their difference would have to be $0\bmod p$. That is, $c_2\cdot A-c_1\cdot A \equiv 0 \bmod p \iff c_2=c_1$ and that is not the case. We have $(p-1)$ distinct products having values between $1$ and $(p-1)$, so by the pigeonhole principle, each value must occur once. We don't know which product corresponds to which value, but we don't need to.

We simply multiply the residues of the products $1$ through $(p-1)$ to obtain $(p-1)!$, and then products $1\cdot A$ through $(p-1)\cdot A$ themselves to obtain $(p-1)!A^{p-1}$, keeping in mind that these two numbers will be equivalent $\bmod p$, viz $$(p-1)!\equiv (p-1)!A^{p-1} \bmod p$$

Since $(p-1)!$ is coprime to $p$, we can divide through to remove it leaving the desired result $$1\equiv A^{p-1}\equiv a^{p-1} \bmod p$$

$\endgroup$
4
$\begingroup$

It might help you to study a few specific cases.

For example, $a = 10$, $p = 7$. We see that $10^6 = 1000000$ and 999999 divided by 7 is 142857.

But let's work through this example using smaller numbers. Obviously $10^2 = 100$. But 98 is a multiple of 7, which means that $10^2 \equiv 2$ $\pmod 7$. And 10 itself is $3 \pmod 7$, so we can calculate $10^3 \equiv ?$ $\pmod 7$ as $2 \times 3 = 6$. And then $10^4 \equiv 6 \times 3 \equiv 4 \pmod 7$. Next we have $10^5 \equiv 4 \times 3 \equiv 5 \pmod 7$.

Lastly, $10^6 \equiv 5 \times 3 \equiv 1 \pmod 7$, which we had already confirmed. I chose this example because $10^n$ modulo 7 takes on every value from 0 to 6 except 0. That's not always the case, but it helps to show which values can't be taken on.

Now consider instead $p = 14$, which is clearly not prime, and $a$ the same as before. You might be aware of the fact that 14 is not a Fermat pseudoprime. But much more importantly in this example, $\gcd(10, 14) = 2$, so we will see that $10^{13} \not\equiv 1 \pmod{14}$.

Then we see that $10 \equiv 10 \pmod{14}$, which is obvious but needs to be said, because $10^2 \equiv 2 \pmod{14}$ just the same as modulo 7. Then $10^3 \equiv 6 \pmod{14}$, $10^4 \equiv 4 \pmod{14}$, $10^5 \equiv 12 \pmod{14}$, $10^6 \equiv 8 \pmod{14}$, $10^7 \equiv 10 \pmod{14}$, $10^8 \equiv 2 \pmod{14}$... whoa, we're back to 2.

The common divisor between 10 and 14 is 2, which means that odd numbers (coprime to 2) can't occur in $10^n \equiv ? \pmod{14}$.

I hope this helps you understand. You might also want to work through examples where $p$ is composite but nonetheless coprime to $a$. Probably hold off on numbers like 341, 561 for now, though.

$\endgroup$

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.