Finding the period in a modular exponentiation sequence

[Bob Walance]

This question is related to Shor's algorithm and its use of modular exponentiation.

In the table below, the period of the sequence in the third column is obviously equal to 4. That is, its value repeats every fourth row.

What I am trying to find out is why it is that when the first value in third column is congruent with 1 then the period of the sequence is the corresponding value of 'r'.

I have searched for an answer but have had no luck. It might be that I don't know how to phrase the question properly to find an answer on Google.

r​	2^r​	(2^r) % 15​
0​	1​	1​
1​	2​	2​
2​	4​	4​
3​	8​	8​
4​	16​	1​
5​	32​	2​
6​	64​	4​
7​	128​	8​
8​	256​	1​
9​	512​	2​
10​	1024​	4​
11​	2048​	8​
12​	4096​	1​
13​	8192​	2​

 

[Bob Walance]

The answer to this question was provided to me at math.stackexchange. I have added an r=0 entry to the table above to make this answer clearer:

1) When r = 0 (let's call this r0) then '(2^0) % 15' is congruent with 1.
2) As r is incremented beyond 0 then '(2^r) % 15' will change from 1 to some other value.
3) When '(2^r) % 15' is equal to 1 again (at rP) then the period of the modular exponentiation sequence will be rP-r0=rP.

If the search for the period of this modular exponentiation sequence is done with a classical computer then it is convenient to find the first r (after r=0) that has the modexp value congruent with 1 again. However, if the search is done using a quantum computer then the quantum Fourier transform would be more efficient in finding the sequence's period.