Primitive Root questions

• November 15th 2010, 08:45 PM
Flippinpony
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.

1) If g is a primitive root, what is $g^{\tfrac{p-1}{2}}(\bmod.p)$
2) Well consider a prime q dividing $n=2^{17}-1$ , then the order of 2 mod q is (Wink) ? . But the order of 2 mod q divides $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 $\sqrt{n}$.
3) $g^{k+1}-g^k\equiv{1}(\bmod.p)$ ...