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 ?
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.