Order of $a \bmod N$ is less than $N$

Question

I'm trying to show that the smallest $r \geq 1$ such that $$a^r \equiv 1 \mod N$$ always satisfies $r < N$ given that $\gcd(a, N) = 1$.

I am under the impression that for coprime $a$ and $N$, if $x \neq y$ and $0 < x \leq N$ and $0 < y \leq N$, then $$a^x \mod N \neq a^y \mod N$$ Thus, every number from $0$ to $N-1$ is made in $$a^{\{1, 2, ..., N \}} \mod N$$ which proves that the order cannot be greater than $N$. But I have no idea if this is true, and cannot prove it.

Answer 1

Take all the congruency classes $a^1,a^2,\ldots,a^N$ modulo $N$. None of them can be $0$, and the are $N$ of them, so by the pigeonhole principle, two of them must be equal. Say $a^m\equiv a^n\pmod N$ with $m<n$. Then $a^{n-m}\equiv 1\pmod N$ and $0<n-m<N$.

Answer 2

Your claim is false: take $a=1$, then $a^x\equiv a^y\pmod N$ for $0<x\le N,\,0<y\le N$.

To prove the statement, consider the set $\{(a^1\pmod N),\cdots,(a^r\pmod N)\}$. Its order is $r$. This set is in fact a subset of $\{(1\pmod N),(2\pmod N),\cdots,(N-1\pmod N)\}$, whose order is $N$. So $r<N$.

---

Hope this helps.

Answer 3

Your impression is wrong. For example, $3^1 \equiv 3^3 \mod 8$.

What is true is that if $a^x \equiv a^y \mod N$ with $x > y$ then $a^{x-y} \equiv 1 \mod N$. Now use the pigeonhole principle.