Chinese remainder theorem

Dear Professor Kim,

Do we need to prove the chinese remainder theorem by using bezouts lemma or by showing it is a bijective mapping?

Reply:

The Chinese remainder theorem says exactly that some map is bijective, so of course you need to show bijectivity. On the other hand, in proving the surjectivity part of it, one way is to use Bezout’s lemma.

One important point about the use of Bezout’s lemma is that it gives a constructive proof of surjectivity. Do you see what I mean by that?

Advertisements

2 Comments

  1. Shruti
    Posted March 22, 2008 at 12:30 pm | Permalink | Reply

    Thank you, i understand that they are the same proofs in 2 different ways, but is the one in the notes, that does not consider a mapping directly sufficient?

    Also when doing questions on the chinese remainder theorem, would we ever get a question with 3 different modulus like in the exercise sheet 2?

  2. Posted March 24, 2008 at 8:34 pm | Permalink | Reply

    If you encounter a question that asks you to give the proof of the Chinese remainder theorem, then any correct proof would be acceptable. But, as I mentioned, you should know the one that uses Bezout’s Lemma because the constructive nature is very useful in practice.

    As for your second question, obviously, I can’t say for certain that you will be tested on it, but the version involving several moduli is certainly part of the material we’ve covered in the course.

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s

%d bloggers like this: