1

Let $x$ and $n$ be integers, such that $\gcd(x,n)=1$. How do I prove that there is a positive integer $m<n$, such that $n\mid x^m-1$?

I'm supposed to prove this using Pigeonhole Principle, and I tried factoring $x^m-1$ and using Diophantine Equation, but I still didn't see how I could apply Pigeonhole here. Any hints would be appreciated.

Bill Dubuque
  • 272,048
Larry
  • 5,090

1 Answers1

2

The $(n+1)$ elements $\{1, x, x^2, \cdots, x^n\}$ can not each be in a separate congruency class, $\pmod{n}$, because there are only $(n)$ such classes. Furthermore, none of these elements can be congruent to $0 \pmod{n}.$

Therefore, ...

user2661923
  • 35,619
  • 3
  • 17
  • 39
  • well but we have to be careful here, and use $\gcd(x,n)=1$. Consider $2^m \mod 10$ for example. Yes we do repeat congruence classes by the time $x=n-1$, but we need $x^m=1 \mod n$. – Mike Feb 06 '21 at 02:20
  • Why is it n+1 elements instead of n-1 elements ${x,x^2,...,x^{n-1}}$ since m is positive and m<n? – Larry Feb 06 '21 at 02:31
  • @Larrry Yes, I was leaving you two pieces of work to do. [1] Since none of the elements can be congruent to $0 \pmod{n}$, the set $S = {1,x,\cdots, x^{(n-1)}}$ must have a congruency class repeat [2] Since $x$ rel. prime to $n$, so is each element in the set $S$. Further, if $c$ rel. prime to $n$ and $ac \equiv bc\pmod{n}$, then $a \equiv b\pmod{n}.$ – user2661923 Feb 06 '21 at 02:47
  • @Mike See the above comment. – user2661923 Feb 06 '21 at 02:49