1
$\begingroup$

The Chinese Remainder Theorem is unbelievably effective as a method for finding an integer $x$ where $x \equiv v_1 \pmod {p_1}$, $x \equiv v_2 \pmod {p_2}$, $\dots$, $x \equiv v_n \pmod {p_n}$.

My challenge is that I find myself unable to develop an intuition about the general distribution of integers that satisfy these type of conditions. For example, if $x \equiv 2 \pmod 5$, $x \equiv 3 \pmod 7$, and $x \equiv 5 \pmod {11}$, will $x$ be greater than $11^2$?

I have no intuition about it.

To build an intuition, I've started using the following intuitive algorithm:

(1) Let's label the primes: $p_1, p_2, \cdots, p_n$ and their values $v_1, v_2, \cdots v_n$

(2) Let $x = v_1$

(3) If $x \not \equiv v_2 \pmod {p_2}$, then add $p_1$ to $x$ until $x \equiv v_2 \pmod {p_2}$

(4) If $x \not \equiv v_3 \pmod {p_3}$, then add $p_1\times p_2$ to $x$ until $x \equiv v_3 \pmod {p_3}$

(5) Repeat this process until for each $p_i$, $x \equiv v_i \pmod {p_i}$

Here's an example of using this algorithm:

(1) Let $x = 2$ (Now, $x \equiv 2 \pmod 5$)

(2) Let $x = 3\times5 + 2 = 17$

(3) Let $x = 5\times35 + 17 = 192$

Here's my question:

Does this algorithm always work? Does it guarantee the least number $x$ such that $x \equiv v_1 \pmod {p_1}, \cdots, x \equiv v_n \pmod {p_n}$?

$\endgroup$
2
$\begingroup$

Both questions can be answered positively.

For the first question: The algorithm obviously always works. You have $n$ equations to satisfy and in each step the amount of equations, which are not satisfied, decreases by at least $1$, so the algorithm terminates after at most $n$ steps.

For the second question: Of course we should assume $0 \leq v_i < p_i$. Proceed by induction. The case $n=1$ is trivial, since the algorithm terminates at the first step with $x=v_1$, which is the unique smallest positive solution.

For the induction step, assume that $x$ is the smallest positive solution to $$x=v_i \pmod{p_i}, i = 1, \dotsc, n-1.$$ This is equivalent of saying $0 \leq x< P := p_1 \dotsb p_{n-1}$.

Since $P$ is coprime to $p_n$, we have that the $p_n$ numbers $x,x+P, \dotsc, x+(p_n-1)P$ are pairwise distinct modulo $p_n$, hence one of them is $v_n \pmod {p_n}$, hence is obtained in the next step of our algorithm. So the obtained solution is smaller than $P+(p_n-1)P=p_nP = p_1 \dotsb p_n$, which is equivalent of saying that it is the smallest positive solution.

Let me make some remarks on this algorithm: For all "exam examples" (meaning examples, that a student can compute by hand in an exam like $p_1=3,p_2=7,p_3=11$), this algorithm is way more effective and handy than the standard algorithm, when you compute the solution by hand.

But is quite easy to see, that the standard algorithm is easier to implement on a computer and is also faster in the general case.

$\endgroup$
  • $\begingroup$ Thanks very much for your analysis! This is very helpful. $\endgroup$ – Larry Freeman Oct 28 '15 at 7:06

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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