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**

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**