In this text the "old" definition of the Legendre symbol is used: $\left( \frac{a}{p}\right) = \begin{cases} +1, & \text{ if $a$ is a quadratic residue } \mod{p} \\ -1 & \text{ if $a$ is a quadratic nonresidue} \mod{p}\end{cases}$

Let $(s_i)_{i \in \Bbb N}$ be a sequence of arbitrary elements of $\{-1,+1\}$. The question is for which numbers $n$ do we have that $\left( \frac{n}{p_i}\right) = s_i$ for $p_i$, the i-th prime. As an example I tried the sequence $(1,1,\ldots)$ for a finite number of primes and a finite number of test samples and ended up with mostly perfect squares. This is not really a remarkable result since perfect squares are always quadratic residues modulo any prime, but intuitively I suspect that these are the only ones, but can't prove it. It results (using "conditional" multiplicativity) that is is sufficient that for every squarefree number $n$ there is a prime modulo to which $n$ is a quadratic nonresidue.

  • $\begingroup$ What do you mean "old"? - Ah, probably that $(\frac 0p)=+1$? $\endgroup$ – Hagen von Eitzen Dec 30 '16 at 13:21
  • $\begingroup$ @Hagen In the sense that the generalization using the value $0$ if a is a multiple of $p$ is not used. So, 0 is always considered a quadratic residue. I don't know if the Wikipedia definition is the one most used nowadays but the cas I use (GAP) doesn't. $\endgroup$ – Marc Bogaerts Dec 30 '16 at 13:26
  • 2
    $\begingroup$ The Chebotarev Density Theorem tells us (informally) that for any polynomial, irreducible over $\mathbb Q$, the proportion of primes for which it is irreducible $\pmod p$ is $\frac 1{degree}$. That answers your question, and severely limits the sequences $\{s_i\}$ that are possible. $\endgroup$ – lulu Dec 30 '16 at 13:31
  • $\begingroup$ I vaguely recall having seen this question settled earlier. This is the first sorta fitting (but not a match with this one, because there all moduli are required) match, but I think we had better ones also. $\endgroup$ – Jyrki Lahtonen Dec 30 '16 at 13:51
  • $\begingroup$ Another close hit. This time without reciprocity! And another. $\endgroup$ – Jyrki Lahtonen Dec 30 '16 at 14:04

Claim. Let $n=p_1p_2\cdots p_m$ be square-free. Then there exists a prime $p$ with $(\frac np)=-1$.

Proof. We may restrict our search to $p$ with $p\equiv 3\pmod 4$. That makes $(\frac{p_i}p)=(\frac{p}{p_i})$. We conclude that $(\frac np)=\prod (\frac p{p_i})$. We can use CRT to prescribe the $p\bmod {p_i}$ arbitrarily and so in particular find a residue class $a\bmod n$ such that $p\equiv a\pmod n$ implies $(\frac np)=-1$. By Dirchlet's density theorem, we can find such $p$. $\square$

  • $\begingroup$ Did you mean $p\equiv 1 \pmod 4$? $\endgroup$ – lulu Dec 30 '16 at 13:44
  • $\begingroup$ You probably mean $p\equiv1\pmod4$ for the quadratic reciprocity to play out as nicely. $\endgroup$ – Jyrki Lahtonen Dec 30 '16 at 13:46
  • $\begingroup$ (4k+1-1)/2 is even $\endgroup$ – Marc Bogaerts Dec 30 '16 at 13:48
  • $\begingroup$ @Hagen I don't see how the Dirichlet density theorem comes in. $\endgroup$ – Marc Bogaerts Dec 30 '16 at 14:14

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.