Register to reply

Proving an inequality for order finding

by jamesa917
Tags: inequality, order, proving
Share this thread:
jamesa917
#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
New model helps explain how provisions promote or reduce wildlife disease
Stress can make hard-working mongooses less likely to help in the future
Grammatical habits in written English reveal linguistic features of non-native speakers' languages
dodo
#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
#3
Nov12-12, 03:31 PM
P: 333
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