I'm having a terrible time grasping Fermat's Little Theorem & then an even rougher time trying to use one to prove the other. Any help on this question would be tremendously appreciated! xx
"The Pigeon Hole Principle makes the obvious statement that if there are n pigeon holes and each is occupied by exactly one pigeon then there are exactly n pigeons in pigeon holes. How was the Pigeon Hole Principle used in the proof of Fermat's Little Theorem?"
Let $p$ be a prime and $a$ be an integer not dividable by $p$, and consider the following $p$ powers of $a$ (modulo $p$): $$a^0,\ a^1,\ a^2,\ \dots,\ a^{p-1}$$ By the pigeon hole principle we have that at least two of them are equal modulo $p$, as we fill at most $p-1$ remainder classes ($p$ won't divide neither $a^k$ for any $k$, so the class of $0$ is excluded). Say $a^j\equiv a^k$ for some $0\le j<k\le p$.
Since $p$ is prime, we must have $a^{k-j}\equiv 1 \pmod p$.
... Can you take it from here?
