Let $p_1, p_2, \dotsc, p_n$ be distinct primes, and let $\epsilon_1, \epsilon_2, \dotsc, \epsilon_n$ be an arbitrary sequence of $1$ and $-1$.

There is an integer $a$ such that $\left( \frac{a}{p_1} \right) = \epsilon_1, \left( \frac{a}{p_2} \right) = \epsilon_2, \dotsc, \left( \frac{a}{p_n} \right) = \epsilon_n$, where $\left( \frac{a}{p_i} \right)$ denotes Legendre's symbol.

What can we say about the number $a$? -- I couldn't find any results for such numbers.

In particular, I am interested in bounds for the smallest possible $|a|$.

Could you recommend any papers or books on the topic?


It's better to write "distinct odd primes" for $p_1, p_2, \dotsc, p_n$.

I have checked for several primes $< 1000$ by using computer. The smallest $a > 0$ does not seem to go beyond the product of two largest primes.

  • $\begingroup$ Do you mean that for every $n$ primes we choose and for every arbitrary sequence of $1$ and $-1$ we choose we can always find such an integer $a$? This is not true if $p_1=3$ $p_2=5$, $\epsilon_1 =1$ and $\epsilon_2 =-1$ $\endgroup$ Oct 29, 2013 at 11:41
  • $\begingroup$ @KonstantinosGaitanas How about $a=13$? :-) $\endgroup$
    – P.-S. Park
    Oct 29, 2013 at 12:00
  • $\begingroup$ Yes you are right,i considered only the case modp $\endgroup$ Oct 29, 2013 at 12:23

3 Answers 3


Noam Elkies argument here shows that some such $A$ must occur among any consecutive $\prod (p_i+3)/2 +1$ integers. In Elkies notation, take $a_i = p_i$; take $A_i$ to be the $(p_i-1)/2$ residue classes modulo $p_i$ which are "good" and take $Z_i$ to be the $(p_i+1)/2$ residue classes which are "bad". I expect one can do better than this.


The number of integers $a$ in $[0, x]$ with the desired property is $$ 2^{-n}\sum_{a=1}^x\prod_{i=1}^n\left(1+\epsilon_i\left(\frac{a}{p_i}\right)\right). $$ Expand the right hand side to obtain one term $2^{-n} x$, and $2^n-1$ sums of the form $2^{-n}\sum_{a\leq x}\left(\frac{a}{q}\right)$, where $q$ is the product of some of the $p_i$. Since sums over non-trivial characters can be bounded, for $x$ sufficiently large the term $2^{-n} x$ dominates, and we obtain that some $a$ exists.

To get a bood upper bound on $a$ you need some specific bound on character sums. There are several such bounds, which to use depends on the information you have for the $p_i$. In general one can use Burgess bounds, and obtains that for any $\epsilon>0$ there exists some $C_\epsilon$, such that $a<2^{C_\epsilon n}q^{\frac{1}{4}+\epsilon}$, where $q=\prod p_i$. If the $p_i$ are all small, one should obtain better results from zero-free regions for Dirichlet $L$-series. If the $p_i$ are of different magnitude, then most of the occurring charactersums are much smaller then $\prod p_i$, thus one can reduce the influence of $n$.

  • $\begingroup$ Is $C_\epsilon\gg1$? $\endgroup$
    – Turbo
    Jul 15, 2015 at 16:22
  • 1
    $\begingroup$ We have $C_\epsilon\rightarrow\infty$ as $\epsilon\rightarrow 0$. $\endgroup$ Jul 16, 2015 at 17:36

For each $i$ pick some $b_i$ so that

$$\left( \frac{b_i}{p_i} \right)=\epsilon_i$$

Now, by the Chinese Remainder Theorem, there exists an $a$ so that

$$a \equiv b_i \mod p_i$$

I think that it follows that there are exactly $\prod \frac{p_i-1}{2}$ solutions modulo $p_1..p_n$ (of course we need $p_i \neq 2$, or $p_i=2 \Rightarrow \epsilon_i=1$ and then the formula changes slightly), so a very rough upperbound is

$$\frac{1}{2}\prod p_i - \prod \frac{p_i-1}{2}$$

Better upperbound can probably be obtained by using the formula for CRT and some upperbounds for the solutions modulo primes.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

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