# Thread: Primitive Root questions

1. ## Primitive Root questions

Hi, I have 3 problems concerning primitive roots that I have been unable to work through. Any advice on how to solve these would be greatly appreciated!

1. Show if g, h are primitive roots of p and p is odd, the least residue of gh is not a primitive root of p.

2. Show 131071 = (2^17)-1 is prime.

3. Show that k exists such that g^(k+1)=(g^k)+1 (mod p), where g is a primitive root of p and p is a prime.

Thanks in advance!

2. Some ideas/hints:

1) If g is a primitive root, what is $\displaystyle g^{\tfrac{p-1}{2}}(\bmod.p)$

2) Well consider a prime q dividing $\displaystyle n=2^{17}-1$ , then the order of 2 mod q is ? . But the order of 2 mod q divides $\displaystyle q-1$ 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 $\displaystyle \sqrt{n}$.

3) $\displaystyle g^{k+1}-g^k\equiv{1}(\bmod.p)$ ...