# Question on a proof of a variation of Euler's theorem

In section 10 of "Elementary Number Theory" by Underwood Dudley, the author proves that $\exists t\in\mathbb{N}$ such that $a^t\equiv 1\pmod{m}$ where $\gcd(a,m)=1$ as follows

If $(a , m) = 1$ , then the least residues $(\text{mod }m)$ of $a , a^2 , a^3 , \dots$ are all relatively prime to $m$. There are $\phi(m)$ least residues $(\text{mod }m)$ that are relatively prime to $m$ and infinitely many powers of $a$ : it follows that there are positive integers $j$ and $k$ such that $j\neq k$ and $a^j\equiv a^k\pmod{m}$. Since $(a, m ) = 1$ , the smaller power of $a$ in the last congruence may be canceled, and we have either $$a^{j-k}\equiv 1\pmod{m}\qquad\text{or}\qquad a^{k-j}\equiv 1\pmod{m}.$$

What I fail to understand is line 3, how does there being infinitely many powers of $a$ imply two different ones must be congruent to each other ?

• That is by the pigeonhole principle. en.wikipedia.org/wiki/Pigeonhole_principle – Arnaud Mortier May 29 '18 at 1:21
• Oh right. Thanks! – Adam May 29 '18 at 1:23
• Wait, but how do we know that the least residues of $a, a^2,\dots$ take on all the values from $0,1,\dots, (m-1)$. What if, say, they all cycle between a few values ? – Adam May 29 '18 at 1:26
• A few values is still finitely many values, and you have infinitely many pigeons. (That's a lot of pigeons) – Arnaud Mortier May 29 '18 at 1:27
• Oh yeah, I keep thinking one of them has to be congruent to 1. Thanks a lot! – Adam May 29 '18 at 1:29

Say the elements $0, 1, \ldots, (m-1)$ represent boxes, and in each box, say with label $i$, you are going to put all integers $j$ such that $a^j\equiv i\bmod m. There are finitely many boxes and infinitely many integers, therefore one box contains more than one integer. Note that if$\gcd(a,m)\neq 1$the equality$a^j=a^k$for some$j\neq k$does not imply that there is some power$\ell \neq 0$such that$a^\ell =1$. Think of the powers of$2\bmod 6$: $$\cases{2^1\equiv2\bmod 6\\2^2\equiv4\bmod 6\\2^3\equiv2\bmod 6\\2^4\equiv4\bmod 6\\\ldots}$$ Two of them are equal, surely enough, but none of them is equal to$1$. Note also in this case that negative powers are undefined since$\gcd(a,m)\neq 1$implies that$a\$ is not invertible.