1
$\begingroup$

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 ?

$\endgroup$
  • 1
    $\begingroup$ That is by the pigeonhole principle. en.wikipedia.org/wiki/Pigeonhole_principle $\endgroup$ – Arnaud Mortier May 29 '18 at 1:21
  • $\begingroup$ Oh right. Thanks! $\endgroup$ – Adam May 29 '18 at 1:23
  • $\begingroup$ 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 ? $\endgroup$ – Adam May 29 '18 at 1:26
  • 1
    $\begingroup$ A few values is still finitely many values, and you have infinitely many pigeons. (That's a lot of pigeons) $\endgroup$ – Arnaud Mortier May 29 '18 at 1:27
  • $\begingroup$ Oh yeah, I keep thinking one of them has to be congruent to 1. Thanks a lot! $\endgroup$ – Adam May 29 '18 at 1:29
1
$\begingroup$

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.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.