I have to prove the following theorem for my course on Number Theory,
Let $a$ and $n$ be natural numbers. Then there exist natural numbers $i$ and $j$, with $i\ne j$, such that $a^i\equiv a^j (mod \space n)$ with $i\ne j$
I have absolutely no idea how to prove this. Please note that I have not learned Fermat's Little Theorem yet and cannot use it in the proof. Could I receive some generous help and hints please?
Best Answer
Every integer number $m$ can be written uniquely in the form $m = qn + r$, where $0 \leq r < n$. So, one can group together all the integer numbers with the same residue $r$ after division by $n$. Then, we get the set $[0]=\{kn:k\in \mathbb{Z}\}, \space [1]=\{kn+1:k\in \mathbb{Z}\}$, ... , $[n-1]=\{kn + (n-1):k\in \mathbb{Z}\}$.
Consider the set $A = \{a^i:i=0,\dots,n\}$. This set has cardinality $n+1$.
But there are only $n$ residue classes: $[0],[1],...,[n-1]$.
Then, by the pigeonhole principle, we conclude that there are two elements in this set $A$, say $a^i,a^j$, that belong to the same class $[b]$. In other words, there exist $i,j=0,\dots,n$, $i\neq j$, such that $a^i\equiv_n b \equiv_n a^j$.