Next: Quantum Simulation Up: RSA Previous: RSA

## Proofs"

We will prove that . Then for all , and thus if , .

We first prove that if is a prime, then .

Consider the set , where is the smallest value such that . (Such a value must exist since the number of possible values for is limited by the numbers less than . Thus at some point two of these powers, say and we must have (I assume ). Thus must be a multiple of p. Since by assumption does not have as a factor, neither does , and thus must have as a factor. This implies that .)

The set of all powers of is a subgroup of the group of all numbers from 1 to under multiplication. We now rely on the theorem of group theory that the size of a subgroup always evenly divides the size of the group itself. That means that r must evenly divide , and thus Note that this theorem is true, even if is greater than . Thus for any , for some integer .

We now show that . Using and using the binomial theorem, we have

 (24)

for some . Similarly, for some . Thus , and must have as a factor, or . This gives or as required.

Next: Quantum Simulation Up: RSA Previous: RSA
Bill Unruh
2000-03-15