We have: (1)

Now and so: satisfies: and therefore k is a power of 2: with

Assume: then (because: ) and this contradicts (1), so and

Now Fermat's Little Theorem Implies: (*)

To prove1)Note that (*) implies that if then is even.

Thus, since we have: and the rest follows by Euler's Criterion.

2)Part 1) implies that