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

This seems so obvious that someone must have investigated it before, but I couldn't turn up anything substantive after a few Google searches.

Let $n$ be an odd natural number. It is a well-known fact that the Jacobi symbol $\left(\frac{a}{n}\right)=-1$ implies $a$ is not a QR modulo $n$, but that $\left(\frac{a}{n}\right)=1$ does not imply $a$ is a QR modulo $n$. I'm interested in all of the "natural questions" about the discrepancy $$s_n=\frac{\#\{a\in(\mathbb{Z}/n\mathbb{Z})^\times\mid\left(\frac{a}{n}\right)=1\}-\#\{a\in(\mathbb{Z}/n\mathbb{Z})^\times\mid a\text{ is a QR}\}}{\phi(n)}.$$ For example, can $s_n$ get arbitrarily close to 1? If not, what is $\sup(s_n)$? Given $r\in\mathbb{Q}\cap[0,1)$, is there always an $n$ such that $r=s_n$? Given $r\in\mathbb{Q}\cap[0,1)$, what is the asymptotic density of $\{n\in\mathbb{N}\mid s_n=r\}$? Are there $r$ such that this asymptotic density is positive?

Here is a graph I produced of $s_n$ for odd $1\leq n\leq 5000$:

enter image description here

The values that occurred were: $0, \frac{1}{4}, \frac{3}{8}, \frac{7}{16}, \frac{1}{2}, \frac{3}{4}$, which would certainly seem to point to there only being a few possible values of $s_n$; however, I didn't check any of the $n\geq 5000$, of which there are a substantial number...

share|cite|improve this question
up vote 3 down vote accepted

For any odd integer $n$, let $k$ be the number of distinct odd prime factors of $n$, and write $ n = \Pi_{i=1}^k p_i^{\alpha_i}$. If $a$ is coprime with $n$, then $a$ is a square mod $n$ if and only if $a$ is a square mod $p_i^{\alpha_i}$ for all i (by the Chinese Remainder Theorem), and this is true if and only if $a$ is a square mod $p_i$ for all i (by Hensel's lemma).

If you pick a number $a$ in $(\mathbb{Z}/n\mathbb{Z})^\times$ at random, you get that $a$ is a square mod $p_i$ with probability $\frac{1}{2}$, so by the CRT, $a$ is a square mod all of them (and thus mod n) with probability $\frac{1}{2^k}$ (what happens modulo a prime number is independant from what happens at the rest of the primes).

Meanwhile, $\left(\frac a n\right) = \Pi_{i=1}^k \left(\frac a {p_i}\right)^{\alpha_i}$, so if $n$ is a square, $\left(\frac a n\right) = 1$, otherwise $\left(\frac a n\right) = 1$ with probability $\frac{1}{2}$.

Thus $s_n = 1 - \frac 1 {2^k}$ if n is a square, and $s_n = \frac 1 2 - \frac 1 {2^k}$ otherwise.

I think this implies that the asymptotic densities of $\{n \in \mathbb{N}, s_n = r\}$ is always $0$, while the densities of $\{n \in \mathbb{N}, |s_n - \frac 1 2| < \epsilon \}$ is $1$ for any $\epsilon > 0$.

share|cite|improve this answer
An excellent, comprehensive answer. Thanks! – Zev Chonoles Apr 18 '11 at 17:31

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.