1
$\begingroup$

I am trying to understand CRT constructive proof from wikipedia [http://en.wikipedia.org/wiki/Chinese_remainder_theorem#A_constructive_algorithm_to_find_the_solution]

I am unable to follow it from x = $\sum\limits_{i=0}^{k} a_i * e_i$ this statements onward. Please help me with this.

$\endgroup$
  • 1
    $\begingroup$ If you'll forgive the self-promotion, I wrote a short blog post on the Chinese Remainder Theorem for a number theory class I taught last summer. The exposition on the construction is slightly different, but it starts after the phrase "construct a solution directly." $\endgroup$ – davidlowryduda Jul 2 '14 at 12:03
  • $\begingroup$ Hi,it helped me. Thanks $\endgroup$ – thetatheta Jul 2 '14 at 16:12
3
$\begingroup$

That sum works out to $x = a_1e_1 + a_2e_2 + ... + a_ke_k$

To see why this is a solution of the simultaneous congruences, take the congruences in turn.

Modulo $n_1$,

$x \equiv a_1e_1 + a_2e_2 + ... + a_ke_k \pmod {n_1} \implies x \equiv a_1.1 + a_2.0 + ... + a_k.0 \pmod {n_1} \implies x \equiv a_1 \pmod {n_1}$

This is because $e_1$ has been carefully chosen to be $1$ modulo $n_1$ and $0$ modulo all other $n$ values under consideration.

Similarly, modulo $n_2$,

$x \equiv a_1e_1 + a_2e_2 + ... + a_ke_k \pmod {n_2} \implies x \equiv a_1.0 + a_2.1 + ... + a_k.0 \pmod {n_2} \implies x \equiv a_2 \pmod {n_2}$

Now, modulo arbitrary $n_r$ such that $(1 \leq r \leq k)$,

$x \equiv a_1e_1 + a_2e_2 + ... + a_re_r + ... + a_ke_k \pmod {n_r} \implies x \equiv a_1.0 + a_2.0 + ... + a_r.1 + ... + a_k.0 \pmod {n_r} \implies x \equiv a_r \pmod {n_r}$

This should allow you to see why that $x$ value solves each individual congruence and therefore all the congruences simultaneously.

$\endgroup$

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.