Numbers with prescribed Legendre symbols

172 Views Asked by At

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.

1

There are 1 best solutions below

4
On

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$