Anonymous

# can someone explain this chinese remainder theorem proof?

Now the first proof solves for the special case of the Chinese remainder theorem where “i” is some fixed subscript and ai = 1 and the rest equal 0.

Let ki be the product of all moduli except mi. Then, because they are relatively prime, by using Bezout’s identity, there are two integers r and s such that rki + smi = 1. This means that rki = = 1(Mod mi), where rki is divisible by all of the other moduli except for mi. Therefore xi = rki satisfies all the congruences.

In addition to this fact, for every subscript of i, there is an xi. This means that no matter what i is, there will always be a xi along with it.

To solve the system of congruences, you set x=a1x1+a2x2+…anxn

Then you will get x = = aixi = = ai

i don't understand how the last two statements lead to each other.

Update:

i used = = to notate congruence

Relevance

Let me clean up your notation, then we'll go through the argument above.

First, so everyone's on the same page, the chinese remainder theorem says that there is a solution to the system

x == a_1 mod m_1

...

...

x == a_n mod m_n

provided m_1, ... , m_n have no common divisor greater than 1.

The first part of what you wrote above solves a special case, namely the case where a_1 = ... = a_{n-1} = 0 and a_n = 1.

As you state above, we can let k = m_1 * m_2 * ... m_{n-1}

and let m = m_n. Then, since these are relatively prime, there exist integers r and s such that

rk + sm = 1.

Now, let x = rk. Since k is divisible by m_j for j = 1, ... , n-1.

x satisfies the first n-1 equations. Since rk = 1 - sm, we see also that x is congruent to 1 mod m. So, x is a solution to the system of equations.

The second part gives a solution to the general statement of the chinese remainder theorem. For each special case we can find a solution. The first special case was where (a_1, ... , a_{n-1}, a_n) = (0, ... , 0, 1). Let's call this solution x_n.

By considering the n-1 other special cases (where 1 appears in the i-th entry and zeros elsewhere, we get solutions

x_1, ..., x_n.

Let x = a_1 x_1 + ... + a_n x_n.

Then, a_i x_i is congruent to 0 mod m_1 if i is not equal to 1.

(because x_i solves (0, ..., 0, 1, 0, ... , 0), where the 1 is in the i-th place).

If i = 1, then x_1 is congruent to 1 and hence a_1 x_1 is congruent to a_1.

So, x == a_1 mod m_1.

Similarly, x == a_j mod m_j for j = 1, ... m.

Thus, x is a solution to the system of equations.

• Login to reply the answers