2
$\begingroup$

Take an infinite set of distinct primes and a (edit: or 2 , etc.) residue class for every prime. For exammple you can take all the primes bigger than some prime or the primes of a specific form (i.e. of some arithmetic progression or whatelse)

The question is under what circumstances every natural number is of some of this residue classes?

Of course there are conditions that the answer is easy(for example if you take as residue class for a prime on the set to be $1\bmod{p_1}$, $2\bmod{p_2}$), but do we have any well known general results on this direction? (On infinite sets of residue classes etc.)

Note:if you think that the question is not very specific please ask me to be more.

EDIT: to be more precise i will give an example : Take all the primes from a point and after, split the natural numbers on intervals of a given length, say A, and for each prime is not allowed to "hit" a number that is in lower interval than itself, (i.e take all the primes greater or equal than 7 and $A=100$)

Improve this question
$\endgroup$
9
  • $\begingroup$ If you know how to pick the infinite set of primes, you are infinitely rich. :-) Jokes aside, your question isn't formulated well. Vote to close. $\endgroup$
    – Wadim Zudilin
    Commented Jan 15, 2011 at 11:50
  • $\begingroup$ What do you mean there are not such covering systems at all ,for trivial reasoning .Is there something that is not well written?Or else please give the trivial reasoning. $\endgroup$
    – Asterios Gkantzounis
    Commented Jan 15, 2011 at 11:51
  • $\begingroup$ If you choose residue zero for all the primes in your set then there is an infinite set of integers you don't hit (multiples of all the other primes). If p is your smallest prime, then you need 1, 2 ... (p-1) as explicit residue classes. I think also that if the sum of the reciprocals of your infinite set is infinite, a random selection of residue classes will almost certainly hit each integer (uniform for each prime). It is easy to construct sets of residues which miss any finite set of numbers with cardinality less than the smallest prime (smallest residue which misses for each prime). $\endgroup$
    – Mark Bennet
    Commented Jan 15, 2011 at 12:04
  • $\begingroup$ I needed more than 10 minutes just to understand your question! ;-) I'll definitely state it simpler and shorter. But I would need more time ($\infty$?) to understand what's use of all this. What kind of criteria do you expect? Pick a number $n\in\mathbb N$, check whether it belongs to a certain residue class. If yes, take $n+1$, and so on. There can't be a finite procedure to answer your Q. $\endgroup$
    – Wadim Zudilin
    Commented Jan 15, 2011 at 12:07
  • $\begingroup$ I asked for known results on this direction $\endgroup$
    – Asterios Gkantzounis
    Commented Jan 15, 2011 at 12:13

1 Answer 1

Reset to default
2
$\begingroup$

If you insist on prime moduli you will need infinitely many classes. If you don't insist on prime moduli then you can get away with finitely many, these are called covering systems and the linked article looks good.

Let $(r,m)=\lbrace r+mj \mid j \ge 0 \rbrace$ and $p_1<p_2<p_3<\cdots$ be a list of some or all the primes. You want a list $(r_1,p_1),(r_2,p_2),\cdots$ whose union is the natural numbers (optinally with some natural numbers allowed to be missed). One method to do this is to greedily define $r_i$ to be the smallest integer not in $\cup_{j<i}(r_j,p_j)$. Is this (almost) optimal? I don't know but I will wildly guess that it is and from now on only discuss the greedy choice. If we use all the primes and try to get all the natural numbers starting with 2 then (making the greedy choice) $r_j=p_j$. This becomes $r_j=p_j-1$ (or $r_j=p_j-2$) if we also want to get 1 ( or 0 and 1). In any case the greedy algorithm gives $\frac{r_i}{p_i} \approx 1$ (Well in the very first we could as well have $r_i=0$)

If we use all the primes except $2$ and try to get all the natural numbers except powers of $2$ (and 0) then again $r_i=p_i$. If we try to get all the natural numbers then it would appear that $\frac{r_i}{p_i} \approx \frac{1}{2}$.

Based on this I will say that there is little hope that you can exclude the primes 2,3,5 (or even just 2) and keep $p_i-r_i<100$. I suspect that for each prime $q$ there is a constant $C_q$ so that using the greedy choice to cover all the natural numbers using primes $q$ and greater results in $\frac{r_i}{p_i} \approx C_q$. It looks as if perhaps $C_7$ is something like 0.43.

Improve this answer
$\endgroup$
4
  • $\begingroup$ First of all i asked for mod primes which is known of chinese remainder theorem that for every finite system is not covering system. I asked for infinite systems.Is there any result that says under what circumstances? $\endgroup$
    – Asterios Gkantzounis
    Commented Jan 15, 2011 at 11:38
  • $\begingroup$ Sorry i was writing when you edit and didnt see it. $\endgroup$
    – Asterios Gkantzounis
    Commented Jan 15, 2011 at 11:40
  • $\begingroup$ things like that and others when you do not use all the primes, especially i am interested when you use the primes biger than some and you demand each prime to sieve from a number and after ,etc. $\endgroup$
    – Asterios Gkantzounis
    Commented Jan 15, 2011 at 12:01
  • $\begingroup$ Could you write a proof for this? $\endgroup$
    – Asterios Gkantzounis
    Commented Jan 17, 2011 at 13:43

You must log in to answer this question.

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