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?
Chinese Remainder Theorem with additional conditions
0
$\begingroup$
number-theory
elementary-number-theory
-
2If 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. – 2011-11-02
2 Answers
2
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.)
0
Suppose $p_1 = 3$, $a_1 = 2$, and $p_2,\ldots$ are the rest of the primes. What do you get?
-
0$x=-1$ works for this particular one - but the idea is certainly sound, as I said in my answer (typed while you entered yours). – 2011-11-02