Show that if is prime and , where is an odd prime and is
a positive integer with , then is a primitive root modulo .
Note that the only numbers dividing are .
So we just have to check that and and .
The latter is simple enough, now for the first means that so (by Euclid's Lemma) which we know is impossible since .
Now try the remaining one!
EDIT: Erroneous post, save for the first 2 lines.
PaulRS, I understand your strategy, however I don't think this works:
One example that would violate that logic is and . Now that specific example is actually invalid since it it doesn't fit the form where q is prime as specified by the problem, but I need to form a proof that this is the case.so (by Euclid's Lemma) which we know is impossible since
I don't see how to prove the case and the case.
Zarathustra... You're response is implicit from the initial problem and the basic definition of a primitive root... You really didn't add anything or help solve this.