Loading ...
Sorry, an error occurred while loading the content.

chinese remainder theorem.

Expand Messages
  • A.W.A.P. Bouman
    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]
    • Andy Robertshaw
      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]
      • A.W.A.P. Bouman
        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.