This question often comes in my mind when doing exercices in elementary number theory:

Is every non-square integer a primitive root modulo some odd prime?

This would make many exercices much easier. Unfortunately I seem unable to discover anything interesting which may lead to an answer.

It seems likely to me that this is true. If $n\equiv2\pmod3$ then it's a primitive root modulo $3$. If $n\equiv2,3\pmod5$, it's a primitive root modulo $5$. If we would continue like this, my guess is that any non-square $n$ will satify at least one of these congruences.

This being difficult, I began considering a simplified question:

Is every non-square integer a quadratic non-residue modulo some prime?

Or equivalently,

If an integer is a square modulo every prime, then is it a square itself?

The second form seems easier to approach, however I still can't find anything helpful.


Let $n$ be a non-square. Write $n=a^2b$ with $b\ne 1$ square-free. Write $b=p_1\cdot\ldots\cdot p_m$ as product of disctinct primes with $m\ge 1$. For primes $q> n$ the factor $a^2$ can be ignored, so we have that $\left( \frac bq\right)=1$ for almost all primes $q$. According to quadratic reciprocity law, $ \left(\frac{b}{q}\right)$ is determined by $q\bmod 8b$. Also, there is at least one residue $d\bmod 8b$ for which $q\equiv d\pmod{8b}$ implies $ \left(\frac{b}{q}\right)=-1$ (e.g. ensure $\left(\frac d{p_1}\right)=-1$ and $\left(\frac d{p_i}\right)=+1$ for all other $i$ and use the chinese remainder theorem). Especially, $d$ is relatively prime to $8b$ so that by Dirichlet there exist infinitely many primes $q$ with $q\equiv d\pmod{8b}$. For such a $q$ with $q>n$ we conclude that $n$ is not a square modulo $q$.

  • 1
    $\begingroup$ Oh yes, I didn't expect it to be that easy. With "According to quadratic reciprocity..." I suppose you mean applying QR to all primes $p_1,\ldots,p_m$ where $q$ is determined modulo $p_k$ and by the parity of $\frac{(q-1)(p_k-1)}4$ and thus certainly modulo $8p_k$. I like this way of roughly handling with primes using CRT and Dirichlet ;). I believe my main question will be much more diffuclt, however. $\endgroup$ – punctured dusk Jan 21 '14 at 12:19

Your "equivalent" question seems trivial and therefore not equivalent.

"If an integer is a square modulo every prime, then is it a square itself?"

Given an integer n, there is a prime p > n. If n is a square modulo every prime, including p, then n = n (modulo p) is a square, so n is a square.

BTW. I wrote a short program that checked whether every non-square integer n <= N is the primitive root modulo some prime p > N, with N = 40 x 10^9. It found that actually every non-square n <= N is a primitive root modulo some prime p with N < p <= N + 1357, which is just the 55th prime > N. This seems to indicate that it is more promising to look for a proof than for a counterexample.

  • 1
    $\begingroup$ There is a mistake in your reasoning. $n<p$ being a quadratic residue modulo $p$ does not imply that $n$ is a square. Take for example $n=2$, $p=7$: $2$ is a square modulo $7$ because $2\equiv3^2\pmod7$, but $2$ isn't a square itself. $\endgroup$ – punctured dusk May 11 '14 at 9:01

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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