I'm trying to understand a process called order finding as I need to know it for Shor's algorithm in quantum computing.(adsbygoogle = window.adsbygoogle || []).push({});

The process is like this:

For two positive integersxandN, with no common factors andx < 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 ofxsatisfies [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.

**Physics Forums | Science Articles, Homework Help, Discussion**

Join Physics Forums Today!

The friendliest, high quality science and math community on the planet! Everyone who loves science is here!

The friendliest, high quality science and math community on the planet! Everyone who loves science is here!

# Proving an inequality for order finding

**Physics Forums | Science Articles, Homework Help, Discussion**