-4
$\begingroup$

A family of residue classes $a_i (\bmod n_i)$ with $2\leq n_1\leq\cdots\leq n_r$, ($r\geq2$) is called a covering system of congruences if every integer belongs to at least one of the residue classes, that is, every integer satisfies at least one of the congruences $a_i (\bmod n_i)$. The known examples are:

$0 (\bmod 2),\quad 0 (\bmod 3),\quad 1 (\bmod 4),\quad 5 (\bmod 6),\quad 7 (\bmod 12).$

$0 (\bmod 2),\quad 0 (\bmod 3),\quad 1 (\bmod 4),\quad 3 (\bmod 8),\quad 7 (\bmod 12),\quad 23 (\bmod 24).$

My question is whether it is possible to construct a (finite with at least two different moduli, or infinite) system of congruences that covers all odd non-square integers using moduli and residue classes satisfying

$$ \left(\frac{a_i}{n_i}\right)=-1,\qquad \text{for}\ \ 1\leq i\leq r $$

where the parenthesis is the Legendre (or Jacobi ) symbol.

P.S. What if we make the condition in the question weaker as follows: whether it is possible to construct a (finite with at least two different moduli, or infinite) system of congruences that covers all odd non-square integers using moduli and residue classes satisfying

$$ \left(\frac{a_i}{n_i}\right)=-1,\ \ \text{or}\ \ 0,\qquad \text{for}\ \ 1\leq i\leq r $$

Improve this question
$\endgroup$
10
  • 3
    $\begingroup$ Some congruence has to cover the number 1, so it has to be $1\bmod n_i$. $\endgroup$
    – Gerry Myerson
    Commented Jul 30, 2018 at 13:26
  • $\begingroup$ @GerryMyerson, what if we assume odd numbers greater than 1? $\endgroup$
    – asad
    Commented Jul 30, 2018 at 13:31
  • 2
    $\begingroup$ Then some congruence has to cover 9. $\endgroup$
    – Gerry Myerson
    Commented Jul 30, 2018 at 13:32
  • $\begingroup$ @GerryMyerson, what if we consider to cover non perfect square odd positive integers? $\endgroup$
    – asad
    Commented Jul 30, 2018 at 13:42
  • $\begingroup$ You've said that $n_i\le n_{i+1}$, which would allow using a modulus more than once. I'm going to change it to $n_i\le n_{i+1}$, and also fix your formatting. $\endgroup$
    – Joe Silverman
    Commented Jul 30, 2018 at 15:30

1 Answer 1

Reset to default
3
$\begingroup$

Given any finite set $n_1,\dots,n_r$ of moduli, there is an odd, nonsquare number $a$ such that the Legendre/Jacobi symbol $(a|n_i)=1$ for all $i$. You can't cover that $a$.

Give it up, asad – quit while you're behind.

Improve this answer
$\endgroup$

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .