1.Suppose is a prime divisor of then and thus, by Lagrange's Theorem, the order of divides . (1)

Suppose is the order of , it cannot be 1 for otherwise , and since the order must divide , but since is prime this implies that that is the order of is . So, by (1), thus thus

2.By induction, it's true for k=1, so let's assume it's true for some we'll show that this implies the assertion for

By hypothesis so now: ( see the terms in the binomial expansion), thus:

In fact 2 is a primitive root module for all