1. ## Primitive Root Problem.

Show that if $p$ is prime and $p = 2q + 1$, where $q$ is an odd prime and $a$ is
a positive integer with $1 < a < p - 1$, then $p - a^2$ is a primitive root modulo $p$.

2. ## Re: Primitive Root Problem.

Note that the only numbers dividing $p-1 = 2 \cdot q$ are $1,2,q,2q=p-1$.

So we just have to check that $(p-a^2)^2\not\equiv 1 (\bmod. p)$ and $(p-a^2)^q \not\equiv 1 (\bmod. p)$ and $(p-a^2)^1 \not \equiv 1(\bmod. p)$.

The latter is simple enough, now for the first $(p-a^2)^2 \equiv a^4 \equiv 1(\bmod. p)$ means that $p| (a^4 -1) = (a^2 - 1)\cdot (a^2 + 1)$ so (by Euclid's Lemma) $a^2\equiv \pm 1(\bmod. p)$ which we know is impossible since $a\in\{2,3,...,p-2\}$.

Now try the remaining one!

EDIT: Erroneous post, save for the first 2 lines.

3. ## Re: Primitive Root Problem.

Originally Posted by VinceW
Show that if $p$ is prime and $p = 2q + 1$, where $q$ is an odd prime and $a$ is
a positive integer with $1 < a < p - 1$, then $p - a^2$ is a primitive root modulo $p$.
You need to show that:

(*) $((2q+1)-a^2)^{\phi(2q+1)}\equiv 1(\mod 2q+1)$

But, $((2q+1)-a^2)^{k}\not\equiv 1(\mod 2q+1)$ for $k<\phi(2q+1)$

Remember that $\phi(2q+1)=2q$ and for (*) use Euler theorem.

4. ## Re: Primitive Root Problem.

PaulRS, I understand your strategy, however I don't think this works:

so (by Euclid's Lemma) $a^2\equiv \pm 1(\bmod. p)$ which we know is impossible since $a\in\{2,3,...,p-2\}$
One example that would violate that logic is $p=17$ and $a=4$. Now that specific example is actually invalid since it it doesn't fit the form $2q + 1$ where q is prime as specified by the problem, but I need to form a proof that this is the case.

I don't see how to prove the $(-a^2)^2 \not\equiv 1 \pmod {p}$ case and the $(-a^2)^q \not\equiv 1 \pmod {p}$ 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.

5. ## Re: Primitive Root Problem.

Suppose $(-a^2)^2 = a^4 \equiv 1 (\bmod.p)$, let $o$ be the order of $a$ module p. Then $o | 4$ and $o | (p-1) = 2\cdot q$.

Since $q$ is an odd prime, this means that $o | \text{gcd}(4,2\cdot q) = 2$ so we must have $a^2 \equiv 1 (\bmod. p)$ which means $a \equiv 1(\bmod.p)$ or $a \equiv -1(\bmod.p)$ ... now this is absurd since $a\in\{2,..,p-2\}$.

For the remaining one, since $q$ is odd $(-a^2)^q = - a^{2\cdot q} = - a^{p-1} \equiv - 1(\bmod.p)$ by Fermat's Little Theorem.

6. ## Re: Primitive Root Problem.

Thanks. Those cases make sense.

But how do you prove that $-a^2 \not\equiv 1 \pmod {p}$. As I said earlier, a=4 and p=17 seem to violate that and you would need to use the fact that q is an odd prime.

7. ## Re: Primitive Root Problem.

Originally Posted by VinceW
Thanks. Those cases make sense.

But how do you prove that $-a^2 \not\equiv 1 \pmod {p}$. As I said earlier, a=4 and p=17 seem to violate that and you would need to use the fact that q is an odd prime.
You need to have that $q$ is an odd prime.

As I said in the previous post : $(-a^2)^q \equiv -1 (\bmod. p)$ so in fact $-a^2\equiv 1 (\bmod. p)$ is impossible (because it'd imply $-1\equiv 1 (\bmod.p)$ ).

8. ## Re: Primitive Root Problem.

How does $-a^2 \equiv 1 \pmod {p}$ imply $-1 \equiv 1 \pmod {p}$. That doesn't seem right at all.

$(-a^2)^q \equiv -1 \pmod {p}$ is very clear (it's one step from Euler's Theorem) and I don't see how that relates.