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.