
> 
> Let $M$ be a natural number $M>1$. For every prime $p\_i$ not dividing $M$ take an arithmetic progression $A\_i=k\_i+np\_i$ , $n\geq 0$ such that $k\_i>p\_i^2/M$. Is there any $M$ and some choice of the $k\_i's$ such that $\cup A\_i= \mathbb{N}$ ?
> 
> 
> CONJECTURE: There is not such choice for any $M$
> 
> 
> 


* MOTIVATION: It is not hard to see that if there is not such a choice for any $M$ Dirichlet's theorem in arithmetic progressions is an easy consequence. Of course this is much more general. We can modify many well known problems in this way.



> 
> For example ,to the previous question, if we take $2$ arithmetic progressions for each $p\_i>M$, instead of $1$ with the same condition then we have something stronger than the twin prime conjecture and polignac's conjecture in general,
> If we take $3$ arithmetic progressions we have something stronger than the problem that infinitely many times exists every logical form with $3$ primes ( for example p, p+2,p+6), etc. To these problems it is enough to take infinitely many $M$, not all...
> 
> 
> 


* Secondly it is one of the easiest questions to this spirit and i want to know if we can say something about this kind of questions with known techniques. So



> 
> What kind of mathematical techniques we could use to reach this kind of problems?
> 
> 
> 


-related to [Covering $\mathbb{N}$ with prime arithmetic progressions](https://mathoverflow.net/questions/80494/covering-mathbbn-with-prime-arithmetic-progressions)



> 
> Can we compute the function of the length of the intervals that we can cover using the primes not dividing $M$ below some $x$ and compare it to the growth function of the number of the primes below some $x$ ?
> 
> 
> 


* Notice that even for the primes below $M$ the arithmetic progressions can start from $1$ , the first term of every $A\_i$ for $p\_i < M$ can be less than $p\_i$ this changes and the first term of the $A\_i's$ becomes larger and larger comparing with the $p\_i's$


I am waiting for any help to this direction, thank you.



Generalising Dirichlet's theorem in arithmetic progressions-prime combinatorics
I can't resist some comments. I find it highly unlikely that what you ask is possible. The question seems a bit odd in that it is so specific when more basic questions are open. 


In the following some estimates are rough and corrections are welcome. Let $p\_i$ be the $i$th prime and $P\_t$ the product of the first $t$ primes. For example $p\_{10000}=104729$ and $P\_{10000} \approx e^{104392.2}.$ This illustrates the estimate $\ln{P\_t} \approx p\_t.$


Define $h(t)$ to be the smallest $N$ so that out of every $N$ consecutive integers at least one is relatively prime to $P\_t$. Equivalently, it is the largest $N$ such that some $N-1$ consecutive integers each have a prime divisor from among the first $t$ primes. Equivalent to that is that $h(t)$ is the largest $N$ such that there is a choice of $t$ residues 
$ k\_{1t},\cdots ,k\_{tt} $ with $\cup\_1^t A\_{it} \supset [1,N-1].$ where $A\_{it}=k\_{it}+np\_i.$ 


According to [this article](http://www.ams.org/journals/mcom/2009-78-266/S0025-5718-08-02166-2/home.html) $h(t) \gt (2e^{\gamma}+o(1))\frac{p\_t\ln{p\_t}\ln\_3{p\_t}}{ln\_2^2{p\_t}}$ where $\ln\_j$ is the $j$-fold iterated logarithm. This lower bound seems reasonably close for $t \lt 50$ (the limit of knowledge at the time, and perhaps now). The best known upper bound is $h(t) \lt \ln^2(P\_t).$ Using the estimate above that $\ln{P\_t} \approx p\_t$ we then get that $h(t) \lt p\_t^2.$ I have seen it conjectured in a [paper from 1976](http://journals.cambridge.org/download.php?file=%252FPEM%252FPEM2_20_04%252FS0013091500026560a.pdf&code=74204c87d6b9c459e6bbfbf916a408e1) that perhaps $h(t)=O(t^{1+\epsilon}).$ Note that $p\_t \approx t\ln{t}=o(t^{1+\epsilon})$ I don't know how current that is. An off topic note is that sometimes one can find a longer interval of integers all enjoying a divisor from $p\_1,\dots,p\_{t-1},p\_{t+1}$


With the notation above a weaker form of your question is 



> 
> Is there an integer $M$ and system of residues $k\_i$ such that for $A\_i=k\_i+np\_i$ we have 
> 
> 
> 1. $\cup A\_{i}=\mathbb{N}$
> 2. With only finitely many exceptions, $k\_i \gt \frac{p\_i^2}{M}$
> 
> 
> 


(I didn't get the motivation to require $p\_i$ relatively prime to $M$. Was it just to forbid at least one prime?)


So the situation is that, as far as I know, no-one can say if $h(n) \gt \frac{p\_t^2}{M}$ infinitely often, and there may even be reasons to doubt that. This is the case that you may completely change the residues each time you bring a new prime into play. In your case you want a single list of residues.Note that the choices which provide a good example for $h(n)$ may not be good for extending to $h(n+1)$.


$h(9)=39$ as shown by 


$$2, 3, 2, 5, 2, 11, 2, 3, 2, 13, 2, 23, 2, 3, 2, 7, 2, 19, 2, 3, 2, 17, 2, 5, 2, 3, 2, 11, 2, 7, 2, 3, 2, 5, 2$$
 $$ 13, 2, 3, 2, \*, 2, \*, 2, 3, 2, \*, 2, \*, 2, 3, 2, \*, 2, 5, 2, 3, 2, 7, 2, \*$$ 


This illustrates that $1+2n,2+3n,4+5n ,6+11n,10+13n,12+23n,16+7n,18+19n$ and $22+17n$ cover all the integers from $1$ to $67$ except for $40,42,46,48,52,60,66.$


The best we can do to extend this introducing the further primes $29,31,37,41,43$ is $h(10) \ge 42,h(11) \ge 46,h(12) \ge 48,h(13) \ge 52,h(14) \ge 60$ etc.The actual values are $46, 58, 66, 74, 90.$ But each requires a new selection of residues.


