$\begingroup$

I am trying to understand CRT constructive proof from wikipedia [

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$ 2

1 Answer

$\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

Sign up or log in

Sign up using Google Sign up using Facebook Sign up using Email and Password Submit

Post as a guest

Post Your Answer Discard

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