Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

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 ?

share|cite|improve this question
@anon,Fixed.... – pedja 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
up vote 0 down vote accepted

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$.

share|cite|improve this answer

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$.

share|cite|improve this answer
But statement isn't true if $p \not \equiv 1 \pmod 4$... – pedja 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$... – pedja 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

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.