Results 1 to 6 of 6

Math Help - Congruence problem with LCM

  1. #1
    Super Member
    Joined
    Mar 2006
    Posts
    705
    Thanks
    2

    Congruence problem with LCM

    Let a,b,f,g,m be integebers with a>b>1>1. If f congruence g (mod a), f congruence g (mod b), and m = lcm(a,b), prove f congruence g (mod m)
    Follow Math Help Forum on Facebook and Google+

  2. #2
    Global Moderator

    Joined
    Nov 2005
    From
    New York City
    Posts
    10,616
    Thanks
    10
    Quote Originally Posted by tttcomrader View Post
    Let a,b,f,g,m be integebers with a>b>1>1. If f congruence g (mod a), f congruence g (mod b), and m = lcm(a,b), prove f congruence g (mod m)
    Given two positive integers: a,b

    We can find two positive integers: x,y

    Such that: lcm(a,b)=xy and x|a , y|b and gcd(x,y)=1

    Now if,
    f = g (mod a)
    Then it is true from any divisor of "a" let x|a then:
    f = g (mod x)
    Similarly
    f = g (mod y)

    Note, gcd(x,y)=1 thus,
    f = g (mod xy) thus, f = g (mod m)
    Follow Math Help Forum on Facebook and Google+

  3. #3
    Global Moderator

    Joined
    Nov 2005
    From
    New York City
    Posts
    10,616
    Thanks
    10
    Here is a nicer way of saying it.

    f = g (mod a)
    f = g (mod b)

    Let c = f - g.

    Then, by definition,
    a|c and b|c

    And we want to show,
    f=g (mod m)
    Meaning,
    m|c

    Theorem
    Now we will show that if a,b,c are positive integers.
    And a|c and b|c and if d=gcd(a,b) then ab|cd.
    (You will see why we show this).

    Proof
    Since d=gcd(a,b) a powerful theorem says we can find integers x,y such that,
    ax+by=d
    That means,
    cd=c(ax+by)=acx+bcy
    Now, it is trivial to see that,
    ab|acx and ab|bcy.
    Thus,
    ab|(acx+bcy) i.e. ab|cd
    Q.E.D.

    Now the result is immediate.
    We can write the fraction (which is an integer) as,
    (cd)/(ab)=(c)/(ab/d)
    But!
    m=lcm(a,b)=ab/gcd(a,b)=ab/d.
    Thus,
    c/m is an integer, i.e. m|c
    Proof complete.
    Follow Math Help Forum on Facebook and Google+

  4. #4
    Super Member
    Joined
    Mar 2006
    Posts
    705
    Thanks
    2
    We are not allow to use fraction in our class for now.

    I understand the proof, but is there a way to write the last part without using "/"?
    Follow Math Help Forum on Facebook and Google+

  5. #5
    Global Moderator

    Joined
    Nov 2005
    From
    New York City
    Posts
    10,616
    Thanks
    10
    Quote Originally Posted by tttcomrader View Post
    We are not allow to use fraction in our class for now.
    I love your professor, I do agree with that approach because division is defined only for divisors.

    Anyway, this is what you can do in your class...
    If a|b then you can write (b/a) as a fraction because it represents the unique number k such that b=ak (which exists by divisibility). (And a not = to 0).

    Basically what I did with the division argument embedded in the rationals is this:

    Theorem
    If a|bc and b|a. Then (a/b)|c (and b is non-zero).

    Proof
    Again, this is valid in your class, because as mentioned division that exists within the integers just represents the quotient upon division.

    By definition, bc=ka and a=bj.
    Multiply, equation 2, though by k to get,
    ka=bkj
    Substitution in equation 1, to get,
    bc=bkj
    Divide, (for b not = 0)
    c=kj
    Thus, j|c BUT j=(a/b) by definition.
    Q.E.D.

    I leave it as an excersice to you to modify my proof using the theorem I just proved right now.
    Again, try to understand what I said, I am not dividing, I am just using a/b to represent that value of j. And this is premisible in your class.
    Last edited by ThePerfectHacker; February 19th 2007 at 05:23 PM.
    Follow Math Help Forum on Facebook and Google+

  6. #6
    Super Member
    Joined
    Mar 2006
    Posts
    705
    Thanks
    2
    Thanks, I finally got it.

    KK
    Follow Math Help Forum on Facebook and Google+

Similar Math Help Forum Discussions

  1. One Congruence Problem
    Posted in the Number Theory Forum
    Replies: 3
    Last Post: September 29th 2010, 10:51 PM
  2. A congruence problem
    Posted in the Number Theory Forum
    Replies: 1
    Last Post: April 19th 2010, 07:47 PM
  3. congruence problem
    Posted in the Number Theory Forum
    Replies: 3
    Last Post: July 2nd 2009, 11:24 AM
  4. congruence problem
    Posted in the Number Theory Forum
    Replies: 1
    Last Post: June 21st 2009, 01:22 PM
  5. Congruence Problem
    Posted in the Number Theory Forum
    Replies: 1
    Last Post: March 9th 2009, 03:14 AM

Search Tags


/mathhelpforum @mathhelpforum