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

$\endgroup$
10
  • 3
    $\begingroup$ Some congruence has to cover the number 1, so it has to be $1\bmod n_i$. $\endgroup$ Jul 30, 2018 at 13:26
  • $\begingroup$ @GerryMyerson, what if we assume odd numbers greater than 1? $\endgroup$
    – asad
    Jul 30, 2018 at 13:31
  • 2
    $\begingroup$ Then some congruence has to cover 9. $\endgroup$ Jul 30, 2018 at 13:32
  • $\begingroup$ @GerryMyerson, what if we consider to cover non perfect square odd positive integers? $\endgroup$
    – asad
    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$ Jul 30, 2018 at 15:30

1 Answer 1

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.

$\endgroup$

Your Answer

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

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