Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

I'm interested in the smallest solution to a family of "excluded congruences." To be precise, let $p_1 < \ldots< p_k$ be a sequence of primes and consider the constraints $$ x \not\equiv a_1 \pmod {p_1}\\ \vdots\\ x \not\equiv a_k \pmod {p_k}\,, $$ where $0 \leq a_i < p_i$ for each $i$. I'd like a reasonably general bound on the smallest (non-negative, say) $x$ that solves this. (It would be nice to have a bound on x as a function of $p_1$ and $p_k$, the smallest and largest primes in the sequence.) Of course $x$ need be no larger than $\prod p_i$ by Chinese remaindering, and $x$ can clearly be taken to be no more than $k$ if $k < p_1$.

It seems clear that something follows from Brun's sieve-like machinery: Along these lines, I'd be grateful for a reference to a version of the sieve that yields something of this form.

Added 12/14/2012: A 1924 theorem of Rademacher provides a nontrivial bound on the question. The statement below is from D. Charles's Sieve Methods book, pg. 45. Let $p_1, \ldots, p_r$ be primes, and let $a_i < p_i$, $b_i < p_i$ be non-negative integers for $1 \leq i \leq r$. Let $D > 1$ be an integer with $\gcd(D, p_i) = 1$ for each $i$, $1 \leq i \leq r$, and $Λ$ is an integer, $0 < Λ < D$, such that $\gcd(Λ,D) = 1$.

Let $P(D; x; p_1, a_1, b_1; p_2, a_2, b_2; \ldots; p_r, a_r, b_r)$ denote the cardinality of the set $$\{ n \leq x \mid n \equiv Λ \;(\bmod\; D); n \not\equiv a_i\; (\bmod\; {p_i}) ; n \not\equiv b_i\; (\bmod \;{p_i})\}\,.$$ If $p_1 < p_2 < \cdots < p_r$ and $p_i > 2$, then $$P(D;x; p_1,a_1,b_1;\ldots ; p_r;a_r;b_r) > \frac{Cx}{D \ln^2 p_r} - C'p_r^{7.9}$$ where $C$ and $C'$ are positive constants.

So, the presence of this theorem somewhat muddies my question. Can things be significantly simplified in my case (where I have a single excluded congruence class modulo each prime, and no other explicit constraints)?

share|cite|improve this question

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

Browse other questions tagged or ask your own question.