Some version of the Prime Number Theorem provides the asymptotic behavior of the number of primes in arithmetic progression $qn+a$ with $(q,a)=1$, $n \ge 1$. I was wondering there are Chebyshev-type arguments (using the binomial coefficients or variants thereof) that establish the existence of at least $$c x/\log x$$ primes in such arithmetic progressions up to $x$ for some even small $c>0$ and some values of $a, q>1$. For instance, is there such an argument for primes of the form $ 4k \pm 1$? This is mostly a curiosity triggered by thinking about a number theory course I will teach soon.
[Math] Elementary lower bounds for the number of primes in arithmetic progressions
analytic-number-theorynt.number-theoryprime-number-theorem
Related Solutions
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 $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 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
$\cup A_{i}=\mathbb{N}$
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.
There is some very nice recent work of Dimitris Koukoulopoulos who uses "pretentious" methods to prove the Siegel-Walfisz Theorem. A preprint can be found here:
http://www.crm.umontreal.ca/~koukoulo/documents/publications/multfncs.pdf
Best Answer
In Section 9 of
Diamond, Harold G., Elementary methods in the study of the distribution of prime numbers, Bull. Am. Math. Soc., New Ser. 7, 553-589 (1982). ZBL0505.10021.
an argument from
Diamond, Harold G.; Erdős, Paul, On sharp elementary prime number estimates, Enseign. Math., II. Sér. 26, 313-321 (1980). ZBL0453.10007.
is sketched, where it is shown that for every $\varepsilon > 0$ there is a Chebyshev style argument that shows that
$$ (1-\varepsilon) x \leq \psi(x) \leq (1+\varepsilon) x$$
for all sufficiently large $x$. The idea is to compare $\Lambda(n) = \mu * \log(n)$ with a truncated version $\Lambda_T(n) = \mu_T * \log(n)$ where $\mu_T$ is $\mu$ truncated to a large interval $[1,T]$ (and modified at $T$ to ensure the normalisation $\sum_n \mu_T(n)/n=0$). Elementary methods can show that $|\sum_{n \leq x} \Lambda_T(n) - m_1(T) x| \leq o(x)$ for an explicitly computable quantity $m_1(T)$ (in fact $m_1(T) = \sum_{n<T} \log \frac{T}{n} \frac{\mu(n)}{n}$) that can be easily demonstrated to converge to one as $T \to \infty$ in a suitably averaged sense. In particular $|\sum_{n \leq x} \Lambda_T(n) - x| \leq |m_1(T)-1| x + o(x)$. The Dirichlet hyperbola method can also be used to produce an upper bound $|\sum_{n \leq x} \Lambda_T(n) - \psi(x)| \leq \delta_T x + o(x)$ for some explicitly computable quantity $\delta_T$ depending on $T$; with the aid of the PNT (in the form $\sum_{n \leq x} \mu(n) = o(x)$) one can show that $\delta_T \to 0$ as $T \to \infty$, and this is enough to conclude the claim. Amusingly, this gives a circular proof of the PNT assuming the PNT; however if one only wishes to get the PNT up to a given error $\varepsilon$ then this argument does not require the PNT, one simply has to locate a concrete value of $T$ for which the upper bounds $|m_1(T)-1|, \delta_T$ in the above inequalities (which can be explicitly computed by Chebyshev type methods) are small enough.
It looks very likely that one can twist this argument by characters and conclude that for every $\varepsilon > 0$ and primitive residue class $a \hbox{ mod } q$ there is a Chebyshev style argument that shows that
$$ (1-\varepsilon) \frac{x}{\phi(q)} \leq \psi(x,q,a) \leq (1+\varepsilon) \frac{x}{\phi(q)}$$
for all sufficiently large $x$, where one again needs the prime number theorem in arithmetic progressions (presumably this time in the form $\sum_{n \leq x} \mu(n) \chi(n) = o(x)$) to guarantee that the elementary upper bounds for the error are indeed small. It seems plausible though that for specific residue classes like $1 \hbox{ mod } 4$ or $-1 \hbox{ mod } 4$ one could actually produce explicit numerical choices of the $T$ parameter that obey all the required properties and in particular produce non-trivial lower bounds of Chebyshev type.