1

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.

thetatheta
  • 227
  • 1
    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." – davidlowryduda Jul 02 '14 at 12:03
  • Hi,it helped me. Thanks – thetatheta Jul 02 '14 at 16:12

1 Answers1

3

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.

Deepak
  • 26,801