How to prove that the order of $x$ modulo $N$ satisfies $r \leq N$?

Question

I'm rather new to number theory and don't have any knowledge in group theory at all. How can I prove that the least positive integer $r$ such that $x^r=1 \ (mod \ N) $ satisfies $r \leq N$?

My thoughts on this problem:

In the definition of order modulo $N$ it is stated that $x<N$ and $gcd(x,N)=1$. This fact allows us (using $gcd$ representation theorem) to state that there exist integers $a,b$ such that $ax+bN=1$. I think I have to use this somehow, but I'm stuck on this step. Can I please get help?

UPD: Thanks to everybody who helped me, the proofs are really elegant and smart!

Answer 1

Yes, indeed you need that $\gcd(x,N)=1$, because otherwise the statement is not true. Look e.g. at $2^r\equiv 1\pmod 4$, which is only true for $r=0$ but not for any positive integer. So I will assume $\gcd(x,N)=1$ in the following.

---

Look at the list

$$x^0,x^1,x^2,...,x^{N-1},x^N$$

modulo $N$. This can give you at most $N$ different numbers, namely $0,...,N-1$. But the list has length $N+1$, so some number must ocure at least twice (pidgeonhole principle).

So, let's say $x^n\equiv x^m\pmod N$ with $n>m$. Maybe you already know that for $\gcd(x,N)=1$ there is a unique multiplicative inverse $x^{-1}$ so that $x\cdot x^{-1}\equiv 1\pmod N$. We multiply $x^{-m}:=(x^{-1})^m$ to both sides:

\begin{align} x^n&\equiv x^m\pmod N &|\cdot x^{-m} \\ x^n\cdot x^{-m}&\equiv x^m\cdot x^{-m}\pmod N \\ x^{n-m}&\equiv 1\pmod N \\ \end{align}

Since $n,m\le N$ and $n>m$ we have that $r:=n-m\le N$ (actually $r<N$).

Answer 2

Draw $N$ points numbered $v_1, \cdots, v_N$ on a circle. Draw an arrow from $v_i$ to $v_j$ if $v_j \equiv v_ix \mod N$. Now if you start following the arrows from $v_1$ (i.e start from $v_1$, then go to $v_j$ such that there's an arrow from $v_1$ to $v_j$ etc).

If $gcd(x,N) \neq 1$, then you would end up in a rho shape (eventually land up in a circle with a tail). But otherwise $x^{-1} \mod N$ exists, so you must end up in a circle.

Try to find out why this happens by actually doing it with a pen and paper for $x = 2, N = 5$ and I think you should be able to understand why this is true (hint: use pigeon-hole principle and the existence of inverse)

Answer 3

Consider the residues of $x^0,x^1,x^2,...,x^N$ modulo $N$. (Take for example, the least positive residue.)

Then, there are $N+1$ residues listed above but there are only $N$ distinct residues modulo $N$.

So $x^i\equiv x^j (\textrm{mod }N)$. Here it may be tempting to say $x^{i-j}\equiv 1 (\textrm{mod }N)$ but here you do need the condition that $x$ and $N$ are coprime because in general this is not true.

(e.g. $6^2\equiv 6(\textrm{mod }10)$ but clearly $6\not\equiv 1(\textrm{mod }10)$)

And so if $x$ and $N$ are coprime, $x^j$ and $N$ are coprime as well so we can "cancel out" $x^j$ which is the equivalent of multiplying out about the inverse of $x^j$.

Answer 4

Suppose there exists $m \in \Bbb Z^+$ such that $x^m\equiv 1\mod N.$ Let $n$ be the least such $m.$

(1). If $1\leq a<b\leq n$ then $x^a\not \equiv x^b \mod N.$ Proof: By contradiction: If $x^a\equiv x^b$ let $m=a+(n-b).$ Then $$x^m\equiv x^{a+(n-b)}\equiv x^a x^{n-b}\equiv$$ $$\equiv x^bx^{n-b}=x^{b+n-b}\equiv x^n\equiv 1$$ but $1\leq a\leq a+(n-b)=m=n-(b-a)<n,$ so $1\leq m<n$ so by def'n of $n$ we have $x^m\not \equiv 1,$ a contradiction.

(2). For $1\leq a\leq n$ let $1\leq f(a)\leq N$ such that $x^a\equiv f(a) \mod N.$ By (1), the set $S=\{f(a): 1\leq a\leq n\}$ has exactly $n$ members. But $S$ is a subset of the $N$-member set $\{y:1\leq y\leq N \}$ so $n\leq N.$