Sorry, an error occurred while loading the content.

## chinese remainder theorem.

Expand Messages
• Dear Calculator friends, After my friends Andy, Gert and Jan went home, I found this explanation of the chinese remainder theorem, which to me is indeed
Message 1 of 3 , Jun 2, 2009
• 0 Attachment
Dear Calculator friends,

After my friends Andy, Gert and Jan went home, I found this "explanation" of the chinese remainder theorem, which to me is indeed Chinese.

Being a humble arithmetician an no mathematician, unfortunately I do not know what is:
a.. simultane congruencies
b.. Euclidic algoritm
c.. . I hope heaven knows what this means, I don't
Other descriptions, explanations were equally (un)helpful.

Chinese remainder theorem.
After my friends returned I downloaded from internet in my own language, this "explanation" of the theorem in question.

simultane congruenties: (mod ni) voor (1)

. Als we nu invoeren ei = s n/ni, dan volgt: (mod ni) en (mod nj) voor alle . Het getal

(mod 3) , (mod 4) (mod 5),

Euclidische algoritme

Regards,

Willem Bouman

[Non-text portions of this message have been removed]
• Hi Willem! Ok, Simulateous congruencies are something you do know - a congruence is a modulo. So if I ask what is the remainder when 67 is divded by 12, I
Message 2 of 3 , Jun 2, 2009
• 0 Attachment
Hi Willem!

Ok, Simulateous congruencies are something you do know - a "congruence" is a modulo.

So if I ask what is the remainder when 67 is divded by 12, I can say (by the Chinese remainder theorem) that the remainder must have simultaneous congruence 3 (mod 4) and 1 (mod 3).

As for Euclid's algorithm, this is something for finding the highest common factor  or greatest common divisor.

Suppose we are asked to find the greatest common divisor between 323 and 1751.

We do 1751/323
1751 = 5x323 + 136
then we do 323/136
323 = 2x136 + 51
next 136/51
136 = 2x51 + 34
now 51/34
51 = 1x34 + 17
and 34/17
34 = 2x17

Each time we divide the previous dividend by the new remainder, and we stop once we do not have a remainder.
Since 17 divides 34 perfectly, we know that this is the greatest common divisor between 323 and 1751.

The second part of the algorithm can then be used to write the gcd as a linear combination:

17 = 1x51 - 1x34
= 1x51 - 1x(136 - 2x51) = 3x51 - 1x136
= 3x (323 - 2x136) -1x136 = 3x323 - 7x136
= 3x323 - 7x(1751 - 5x323) = 38x323 - 7x1751

So 17 = 38x323 - 7x1751. I don't quite see how this is linked to the Chinese remainder theorem.

Hope this helps,

Andy

________________________________
From: A.W.A.P. Bouman <awap.bouman@...>
To: mental calculation <MentalCalculation@yahoogroups.com>
Sent: Tuesday, 2 June, 2009 13:58:19
Subject: [Mental Calculation] chinese remainder theorem.

Dear Calculator friends,

After my friends Andy, Gert and Jan went home, I found this "explanation" of the chinese remainder theorem, which to me is indeed Chinese.

Being a humble arithmetician an no mathematician, unfortunately I do not know what is:
a.. simultane congruencies
b.. Euclidic algoritm
c.. . I hope heaven knows what this means, I don't
Other descriptions, explanations were equally (un)helpful.

Chinese remainder theorem.
After my friends returned I downloaded from internet in my own language, this "explanation" of the theorem in question.

simultane congruenties: (mod ni) voor (1)

. Als we nu invoeren ei = s n/ni, dan volgt: (mod ni) en (mod nj) voor alle . Het getal

(mod 3) , (mod 4) (mod 5),

Euclidische algoritme

Regards,

Willem Bouman

[Non-text portions of this message have been removed]

[Non-text portions of this message have been removed]
• Hi Andy, Your reaction is printed and will be studied. I do not know where the CRT is used for, anyhow in the case of the remainder division it was crystal
Message 3 of 3 , Jun 3, 2009
• 0 Attachment
Hi Andy,

Your reaction is printed and will be studied.

I do not know where the CRT is used for, anyhow in the case of the remainder division it was crystal clear.

Regards,

Willem

----- Oorspronkelijk bericht -----
Van: Andy Robertshaw
Aan: MentalCalculation@yahoogroups.com
Verzonden: dinsdag 2 juni 2009 21:33
Onderwerp: Re: [Mental Calculation] chinese remainder theorem.

Hi Willem!

Ok, Simulateous congruencies are something you do know - a "congruence" is a modulo.

So if I ask what is the remainder when 67 is divded by 12, I can say (by the Chinese remainder theorem) that the remainder must have simultaneous congruence 3 (mod 4) and 1 (mod 3).

As for Euclid's algorithm, this is something for finding the highest common factor or greatest common divisor.

Suppose we are asked to find the greatest common divisor between 323 and 1751.

We do 1751/323
1751 = 5x323 + 136
then we do 323/136
323 = 2x136 + 51
next 136/51
136 = 2x51 + 34
now 51/34
51 = 1x34 + 17
and 34/17
34 = 2x17

Each time we divide the previous dividend by the new remainder, and we stop once we do not have a remainder.
Since 17 divides 34 perfectly, we know that this is the greatest common divisor between 323 and 1751.

The second part of the algorithm can then be used to write the gcd as a linear combination:

17 = 1x51 - 1x34
= 1x51 - 1x(136 - 2x51) = 3x51 - 1x136
= 3x (323 - 2x136) -1x136 = 3x323 - 7x136
= 3x323 - 7x(1751 - 5x323) = 38x323 - 7x1751

So 17 = 38x323 - 7x1751. I don't quite see how this is linked to the Chinese remainder theorem.

Hope this helps,

Andy

________________________________
From: A.W.A.P. Bouman <awap.bouman@...>
To: mental calculation <MentalCalculation@yahoogroups.com>
Sent: Tuesday, 2 June, 2009 13:58:19
Subject: [Mental Calculation] chinese remainder theorem.

Dear Calculator friends,

After my friends Andy, Gert and Jan went home, I found this "explanation" of the chinese remainder theorem, which to me is indeed Chinese.

Being a humble arithmetician an no mathematician, unfortunately I do not know what is:
a.. simultane congruencies
b.. Euclidic algoritm
c.. . I hope heaven knows what this means, I don't
Other descriptions, explanations were equally (un)helpful.

Chinese remainder theorem.
After my friends returned I downloaded from internet in my own language, this "explanation" of the theorem in question.

simultane congruenties: (mod ni) voor (1)

. Als we nu invoeren ei = s n/ni, dan volgt: (mod ni) en (mod nj) voor alle . Het getal

(mod 3) , (mod 4) (mod 5),

Euclidische algoritme

Regards,

Willem Bouman

[Non-text portions of this message have been removed]

[Non-text portions of this message have been removed]

[Non-text portions of this message have been removed]
Your message has been successfully submitted and would be delivered to recipients shortly.