# Chinese Remainder Theorem with additional conditions

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?

• 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

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$).
Suppose $p_1 = 3$, $a_1 = 2$, and $p_2,\ldots$ are the rest of the primes. What do you get?
• $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