Some ideas/hints:

1) If g is a primitive root, what is

2) Well consider a prime q dividing , then the order of 2 mod q is ? . But the order of 2 mod q divides by Fermat's Little Theorem, this reduces the number of primes we have to check (to see if they divide n) in fact, remember that if n were not prime, there's a prime divisor which is no greater than .

3) ...