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


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

  • $\begingroup$ An excellent, comprehensive answer. Thanks! $\endgroup$ – Zev Chonoles Apr 18 '11 at 17:31

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.