# Primitive roots modulo $~p~$, where $~p\equiv 1 \pmod 4 ~$?

I would like to propose generalization of this question :

Let $p$ be a prime number such that : $p\equiv 1 \pmod 4$

Show that $~k\cdot p \pm a~$ is a primitive root modulo $p~$ iff

$a$ is a primitive root modulo $p$ , where $k \in \mathbb{Z}$ .

So we want to show that :

If $(kp\pm a) ^m \equiv 1 \pmod p ~$ then $(p-1) \mid m$

According to Freshman Dream Theorem it follows that :

$(kp+(\pm a)) ^p \equiv (kp)^p +(\pm a)^p \pmod p$

And from Fermat Little Theorem we know that :

$a^{p-1} \equiv 1 \pmod p$

How could we proceed from this point ?

• @anon,Fixed.... – Peđa Terzić Feb 3 '12 at 9:30
• And little can be predicted from the title... – awllower Feb 3 '12 at 9:30
• No, you do not get it. anon is to say that the two numbers under consideration here are the same modulo the prime, and hence their property ought to be the same, thus leaving this question in a somewhat embarrassing position... P.S. A primitive root is one congruence class, instead of one number. – awllower Feb 3 '12 at 9:32
• Sorry, I overlooked the $(p-1)|m$ part and so this looked like the same exact problem as the linked one. But there's still no point in considering $kp\pm a$ instead of just $\pm a$. – anon Feb 3 '12 at 9:34
• Doesn't this follow directly from this one? – Arturo Magidin Feb 3 '12 at 15:55

## 2 Answers

Assume $p\equiv1\pmod4$ and $-a$ is a not a primitive root modulo $p$. Then $(-a)^{(p-1)/q}\equiv1\pmod p$ for some prime $q$ dividing $p-1$. But from $p\equiv1\pmod4$ we deduce that $(p-1)/q$ is even (the critical case is $q=2$), so $(-a)^{(p-1)/q}=a^{(p-1)/q}$, so $a$ is not a primitive root. Thus we have proved that if $a$ is a primitive root then so is $-a$.

What you have is not a generalization of the linked question, but is instead something very close to the definition of primitivity. By definition, if $g\mod p$ is a primitive root, then $\operatorname{ord}g=\varphi(p)=p-1$, and it's a basic fact that $u^k=1\mod v$ implies $(\operatorname{ord}u)|k$, so there you have it.

If you're not familiar with this basic fact, say $b=\operatorname{ord}u$ and write $k=tb+s$ with $0\le s<b$. Then we have $1=u^k=(u^t)^b u^s=u^s$ which implies $\operatorname{ord}u\le s$, a contradiction, unless $s=0$.

• But statement isn't true if $p \not \equiv 1 \pmod 4$... – Peđa Terzić Feb 3 '12 at 9:50
• @pedja: So? You have $p\equiv1$ in the title. – anon Feb 3 '12 at 9:59
• ,your answer is related to all prime numbers...while statement from my question is true only if $p\equiv 1 \pmod 4$... – Peđa Terzić Feb 3 '12 at 10:07
• Yes, primitive of $a$ implying primitivity of $-a$ requires $p\equiv1$, which is the hypothesis here, and what I've given applies in this case because $p$ is prime and $\pm a$ primitive. – anon Feb 3 '12 at 10:10