Results 1 to 3 of 3

Math Help - Dividing a congruence

  1. #1
    Newbie
    Joined
    Apr 2010
    Posts
    4

    Question Dividing a congruence

    Hi all,

    I have a congruence 224x +225y = 226 (mod 228)
    I've been told it can be reduced to:
    0x + 1y = 2 (mod 4)
    2x + 0y = 1 (mod 3)
    15x + 16y = 17 (mod 19)

    I don't think I fully understand how to divide (reduce?) a congruence because I can't figure out how to get from the first congruence to the other three.

    I recognize that 3, 4, and 19 are the prime factors of 228, and also that if you use these values as modulo on the original values (224, 225, 226) you get the new values in the last three congruences. i.e. 224 mod 3 = 2, which fits into 2x + 0y = 1 mod 3

    I (think I) understand how to divide a congruence by a number if the divisor and the modulo are relatively prime. If ax + by = c (mod n) and gcd(d,n) is 1 then you can divide a, b, and c by d for the new congruence.
    Example: 6x + 10y = -14 (mod 3) divided by 2 is 3x + 5y = -7 (mod 3)

    If d and n are not relatively prime, then it is my understanding that you can still divide, but that the resulting modulo will change to equal (n / gcd(n,d)) and the c value equals (c/gcd(n,d)) and not c/d.
    Example: 28x - 14y = 14 (mod 35) divided by 14 is 2x - 1y = 2 (mod 5)

    I tried this second method to divide 224x + 225y = 226 (mod 228) by 57 (in order to get a new modulo of 4), but 224 and 225 are not evenly divisible by 57.

    Is there a special rule on dividing a congruence by a prime factor of its modulo? Am I doing the wrong thing when trying to divide a congruence by a number that is not relatively prime to the modulus?


    Thank you for your time,
    m
    Last edited by LittleM; April 24th 2010 at 11:30 AM. Reason: Forgot to make note of the c value calculation in 2nd example, (c/gcd(n,d)).
    Follow Math Help Forum on Facebook and Google+

  2. #2
    Member
    Joined
    Apr 2010
    Posts
    78
    Because if you can divide it to couple of moduli which are pairwise coprime, then you can use CRT to recover the original congruence
    Follow Math Help Forum on Facebook and Google+

  3. #3
    Newbie
    Joined
    Apr 2010
    Posts
    4

    It is the division I don't understand

    Quote Originally Posted by FancyMouse View Post
    Because if you can divide it to couple of moduli which are pairwise coprime...
    I understand how to use the Chinese Remainder Theorem on the last three congruences to get the first congruence, but I don't know how to start with the first congruence and come up with the last three congruences. I understand how to get the prime factorization of the modulo from the first congruence, but how do I divide the original congruence to get the new equations?

    What is the equation that turns: 224x + 225y = 226 (mod 228)
    into: 0x + 1y = 2 (mod 4)


    Thanks for the thought,
    m
    Follow Math Help Forum on Facebook and Google+

Similar Math Help Forum Discussions

  1. dividing
    Posted in the Pre-Calculus Forum
    Replies: 6
    Last Post: July 17th 2009, 11:23 AM
  2. Dividing
    Posted in the Number Theory Forum
    Replies: 1
    Last Post: March 20th 2009, 12:07 AM
  3. dividing polynomials
    Posted in the Algebra Forum
    Replies: 1
    Last Post: February 26th 2009, 06:38 PM
  4. dividing
    Posted in the Algebra Forum
    Replies: 2
    Last Post: November 29th 2008, 01:29 PM
  5. Dividing
    Posted in the Advanced Math Topics Forum
    Replies: 6
    Last Post: January 3rd 2008, 01:39 PM

Search Tags


/mathhelpforum @mathhelpforum