1. ## Primitive Root Problem.

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

2. ## Re: Primitive Root Problem.

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

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

The latter is simple enough, now for the first $\displaystyle (p-a^2)^2 \equiv a^4 \equiv 1(\bmod. p)$ means that $\displaystyle p| (a^4 -1) = (a^2 - 1)\cdot (a^2 + 1)$ so (by Euclid's Lemma) $\displaystyle a^2\equiv \pm 1(\bmod. p)$ which we know is impossible since $\displaystyle 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 $\displaystyle p$ is prime and $\displaystyle p = 2q + 1$, where $\displaystyle q$ is an odd prime and $\displaystyle a$ is
a positive integer with $\displaystyle 1 < a < p - 1$, then $\displaystyle p - a^2$ is a primitive root modulo $\displaystyle p$.
You need to show that:

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

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

Remember that $\displaystyle \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) $\displaystyle a^2\equiv \pm 1(\bmod. p)$ which we know is impossible since $\displaystyle a\in\{2,3,...,p-2\}$
One example that would violate that logic is $\displaystyle p=17$ and $\displaystyle a=4$. Now that specific example is actually invalid since it it doesn't fit the form $\displaystyle 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 $\displaystyle (-a^2)^2 \not\equiv 1 \pmod {p}$ case and the $\displaystyle (-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 $\displaystyle (-a^2)^2 = a^4 \equiv 1 (\bmod.p)$, let $\displaystyle o$ be the order of $\displaystyle a$ module p. Then $\displaystyle o | 4$ and $\displaystyle o | (p-1) = 2\cdot q$.

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

For the remaining one, since $\displaystyle q$ is odd $\displaystyle (-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 $\displaystyle -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 $\displaystyle -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 $\displaystyle q$ is an odd prime.

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

8. ## Re: Primitive Root Problem.

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

$\displaystyle (-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.