Register to reply 
Proving an inequality for order finding 
Share this thread: 
#1
Nov712, 04:05 PM

P: 1

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. 


#2
Nov1212, 05:59 AM

P: 688

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). 


#3
Nov1212, 03:31 PM

P: 345

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 N1##. This means that there are ##\,r,s##: ##0\le r < s\le N1##, and ##k\ge 0## such that ##\,kN=x^sx^r=x^r(x^{sr}1)##. The prime factors of ##N## are then distributed between ##x^r## and ##x^{sr}1##. But ##N## and ##x## have no common factors. Thus, all the prime factors of ##N##, with appropriate powers, divide ##x^{sr}1##, which therefore is divisible ny ##N##. In other words, ##x^{sr}=1## (mod ##N##), and ##\,0<sr\le N##. Q.E.D. 


Register to reply 
Related Discussions  
Proving an inequality  Calculus & Beyond Homework  4  
Help proving an inequality  Calculus & Beyond Homework  15  
Proving an inequality  sin n>c  Calculus & Beyond Homework  28  
Proving the inequality  Calculus  3  
Proving an Inequality  Introductory Physics Homework  6 