Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It only takes a minute to sign up.
Sign up to join this community
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.
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$$
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.
