Proving an inequality for order finding

jamesa917

I'm trying to understand a process called order finding as I need to know it for Shor's algorithm in quantum computing.

The process is like this:

For two positive integers x and N, with no common factors and x < N, the order of x modulo N is defined to be the least positive integer, r, such that [itex]x^r = 1(mod~N)[/itex].

I'm fine with this, but my problem comes in the following, which is left as an exercise in the book I'm using (Nielsen & Chuang):

Show that the order of x satisfies [itex]r \le N[/itex].

Does anyone have any suggestions for this? It's a bit similar to Fermat's Little Theorem but not quite the same. I'm assuming it's a fairly brief proof (as in several lines rather than several pages) based on the difficulty of other questions in the book on that topic.

Thanks in advance for any help.

dodo

Hi, jamesa917,
I suppose one quick route is to prove that (a) r divides phi(N), where phi(N) is Euler's totient function, and (b) phi(N) <= N, since phi(N) counts the number of positive integers less than or equal to N and coprime to N.

The (a) part may involve Euler's Theorem (A generalization of Fermat's Little Theorem) and some knowledge of group theory, in particular Lagrange Theorem (see f.i. the wikipedia page, under "Using the theorem"). Alternatively, you can google for a simpler proof (I found this post).

Erland

First of all, to every ##n\ge 0##, there exists a ##p##: ##0\le p\le N-1##, such that ##n=p## (mod ##N##).

Therefore, at least two of the ##N+1## numbers ##x^0,\,x^1,\,x^2\,,\dots\,,x^N## are equal (mod ##N##) to the same number ##p##: ##0\le p\le N-1##.

This means that there are ##\,r,s##: ##0\le r < s\le N-1##, and ##k\ge 0## such that ##\,kN=x^s-x^r=x^r(x^{s-r}-1)##.

The prime factors of ##N## are then distributed between ##x^r## and ##x^{s-r}-1##. But ##N## and ##x## have no common factors. Thus, all the prime factors of ##N##, with

appropriate powers, divide ##x^{s-r}-1##, which therefore is divisible ny ##N##. In other words, ##x^{s-r}=1## (mod ##N##), and ##\,0<s-r\le N##. Q.E.D.