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 prove 1) 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