We use the result that the primes which have as a quadradic residue are of the form . This result can be established using quadradic reciprocity. Since , a prime, does not have this form it means . Thus, by Euler's criterion. Let be order of then . But if then and it would follow that which is a contradiction. Therefore, and consequently is a primitive root of .
It follows that has order mod .