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

Consider an infinite set of primes $\{p_{1}, p_{2}, \ldots, p_{s}, p_{s + 1}, \ldots\}$ and the system of congruences $x \equiv a_{i} \mod p_{i}$ for $i = 1, 2, \ldots, s$. Then by the Chinese Remainder Theorem there is a solution to this system of linear congruences. But what if I add the condition that $x \not\equiv 0 \mod p_{s + k}$ for all $k \geq 1$. Does such an $x$ still exist?

share|cite|improve this question
Are you given the values of $a_1, \ldots, a_s$, or should you pick them cleverly so that your condition is satisfied? – Srivatsan Nov 2 '11 at 0:38
I am given the $a_{i}$. – Shayla Nov 2 '11 at 0:38
Do you believe this could be false if you take the set of all primes? Have you tried showing it for the collection of all primes? If it works with all of them it'll surely work for any infinite subset. – Olivier Bégassat Nov 2 '11 at 0:41
If the $a_i$ are all equal to one you can take $x=1$ but if the $a_i$ are all non zero and not all $=1$ this will fail for the collection of all primes because a solution would have to be $>1$ and thus have a prime factor and have at least one $0$ congruence. – Olivier Bégassat Nov 2 '11 at 0:46
up vote 2 down vote accepted

It is not necessarily true that such an $x$ exists. Take for example $s=1$ and $p_1=5$, $a_1=2$, and let $p_2,p_3,\dots$ be all of the other primes. The only integers $x$ that are not divisible by any of the primes $p_2,p_3,\dots$ are those of the form $\pm 5^k$, and none of those are congruent to $2$ (mod $5$).

(I see Yuval Filmus had the same idea.)

share|cite|improve this answer

Suppose $p_1 = 3$, $a_1 = 2$, and $p_2,\ldots$ are the rest of the primes. What do you get?

share|cite|improve this answer
$x=-1$ works for this particular one - but the idea is certainly sound, as I said in my answer (typed while you entered yours). – Greg Martin Nov 2 '11 at 0:54

Your Answer


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

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