Results 1 to 2 of 2

Math Help - Using Extended Euclidean Alogirthm to compute Chinese Remainder Theorem

  1. #1
    Newbie
    Joined
    Feb 2011
    Posts
    23

    Using Extended Euclidean Alogirthm to compute Chinese Remainder Theorem

    Given the classical problem, z = a mod m and z = b mod n. Suppose we have:

    z = 2 mod 3
    z = 3 mod 5
    z = 2 mod 7

    The Extended Euclidean Algorithm will find the gcd(m,n). GCD is also the smallest positive integer which can be rewritten as the linear combination of two numbers.




    I tested this algorithm and it works.

    Because we have three z, we have to perform the followings
    (Reference: Solving Congruences: The Chinese Remainder Theorem)

    Code:
    [1] Compute the gcd of the first two z to find the expression  (m*x0) + (n*y0)
    [2] Construct a new z based on [1], where
           z_new = (m*x0)*b + (n*y0)*a  mod (m*n)
    [3] Compute the gcd of z_new and the third z
    [4] The final z that satisfy the system is again
           z_system = (m*x0)*b + (n*y0)*a  mod (m*n)
    n = 2 mod 3 and n = 3 mod 5, where a = 2, b = 3, m = 3 and n = 5
    the gcd formula will give us the expression (m*x0) + (n*y0), which is
    (2 * 3)*3 + (-1 * 5) * 2 mod (3*5), or
    8 mod 15

    Then compute 8 mod 15 with n = 2 mod 7 (the last z in the system), where a = 8, b = 2, m = 15, and n = 7, we have
    (1 * 15) * 2 + (-2 * 7) * 8 mod (15*7), or
    -82 mod 105

    Yet -82 is not the minimal.

    All the solutions I have seen using direct substitution will give me 23 (mod 105).

    This is the minimal solution.

    Using Extended Euclidean Algorithm give us something that is not minimal. What can I do to minimize this?

    I hope this is clear.

    Thank you for helping.
    Follow Math Help Forum on Facebook and Google+

  2. #2
    MHF Contributor

    Joined
    Apr 2005
    Posts
    15,367
    Thanks
    1312

    Re: Using Extended Euclidean Alogirthm to compute Chinese Remainder Theorem

    What do you mean by "minimal" solution? If you want a value between 0 and 104, just add 105 to -82: 105- 82= 23.
    Follow Math Help Forum on Facebook and Google+

Similar Math Help Forum Discussions

  1. Chinese Remainder Theorem
    Posted in the Discrete Math Forum
    Replies: 1
    Last Post: April 4th 2011, 09:20 PM
  2. Euclidean Algorithm & Chinese Remainder Theroem
    Posted in the Discrete Math Forum
    Replies: 1
    Last Post: May 16th 2010, 09:44 AM
  3. Chinese Remainder Theorem
    Posted in the Number Theory Forum
    Replies: 1
    Last Post: May 10th 2010, 01:24 PM
  4. chinese remainder theorem
    Posted in the Number Theory Forum
    Replies: 3
    Last Post: June 24th 2009, 11:19 AM
  5. Chinese Remainder Theorem
    Posted in the Number Theory Forum
    Replies: 3
    Last Post: April 10th 2006, 07:28 AM

Search Tags


/mathhelpforum @mathhelpforum