Understanding a specific method for applying the Chinese Remainder Theorem and its implications with regard to the lower bound of a solution

186 Views Asked by At

Observation:

Consider the Chinese Remainder Theorem applied to this problem of $n$ remainders where each $p_i$ is a prime:

$$x \equiv r_1 \pmod {p_1}$$ $$x \equiv r_2 \pmod {p_2}$$ $$\dots$$ $$x \equiv r_n \pmod {p_n}$$

It occurs to me that any solution can be represented by this form where each $0 \le a_i < p_i$ is an integer:

$$r_1 + a_2(p_1) + a_3(p_1p_2) + a_4(p_1p_2p_3) + \dots + a_n(p_1p_2\dots p_{n-1})$$

Here's my reasoning:

(1) $r_1 \equiv r_1 \pmod {p_1}$

(2) The addition of any multiple of $p_1$ preserves the relation and $r_1, r_1 + p_1, r_1 + 2p_1, \dots, r_1 + (p_2-1)p_1$ forms a complete residue system modulo $p_2$ so that there exists $0 \le a_2 < p_2$ such that $r_1 + a_2p_1 \equiv r_2 \pmod {p_2}$

(3) The addition of any multiple of $p_1p_2$ preserves (1) and (2) and $r_1 + a_2p_1, r_1 + a_2p_1 + p_1p_2, r_1 + a_2p_1 + 2p_1p_2, \dots, r_1 + a_2p_1 + (p_3-1)p_1p_2$ forms a complete residue system modulo $p_3$ so that there exists $0 \le a_3 < p_3$ such that $r_1 + a_2p_1 + a_3p_1p_2 \equiv r_3 \pmod {p_3}$

(4) We can repeat the same method up to $a_n$ to get the desired result.

I'm interested in this method because it provides an opportunity to establish a lower bound for a given solution.

Question:

Assuming that the form above is correct (I believe that it is), is it possible to determine conditions whereby each $a_i$ is nonzero?

It seems to me that this might be the case if no $r_i$ are equal.

If all $r_i$ were the same. Then $r_1$ is itself the solution with all $a_i = 0$

Are there any other conditions that can be called out where the solution will necessarily have all $a_i$ nonzero? I am also interested if a condition exists where $a_n$ is nonzero.

Is this an open question?

I am interested because if $a_n$ is nonzero, then $x > p_1p_2p_3\dots p_{n-1}$


Addendum: Suggested by Gerry Myerson in his comment

I was testing out different combinations using simple primes such as $3,5,7,11$.

I've made three observations. All of them pretty trivial and not too helpful to a general condition (as far as I can see).

(1) If any 2 $r_i$ are congruent modulo the same prime, then that can allow one $a_i=0$

For example, if:

$$x \equiv 3 \pmod 5$$ $$x \equiv 8 \pmod {11}$$

(2) If any of the $n!$ ways to construction a solution have $a_i=0$, then all of the other combinations have at least one $a_i=0$.

(3) If a solution is less than the product of any $n-1$ primes, then $a_n=0$.

None of these provide a condition that ensures that $a_n > 0$.