Proving an inequality for order finding


by jamesa917
Tags: inequality, order, proving
jamesa917
jamesa917 is offline
#1
Nov7-12, 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.
Phys.Org News Partner Science news on Phys.org
Internet co-creator Cerf debunks 'myth' that US runs it
Astronomical forensics uncover planetary disks in Hubble archive
Solar-powered two-seat Sunseeker airplane has progress report
dodo
dodo is offline
#2
Nov12-12, 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).
Erland
Erland is offline
#3
Nov12-12, 03:31 PM
P: 304
Quote Quote by jamesa917 View Post
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.
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.


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