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
    9
    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
    9
    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
    9
    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 04: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, 09:51 PM
  2. A congruence problem
    Posted in the Number Theory Forum
    Replies: 1
    Last Post: April 19th 2010, 06:47 PM
  3. congruence problem
    Posted in the Number Theory Forum
    Replies: 3
    Last Post: July 2nd 2009, 10:24 AM
  4. congruence problem
    Posted in the Number Theory Forum
    Replies: 1
    Last Post: June 21st 2009, 12:22 PM
  5. Congruence Problem
    Posted in the Number Theory Forum
    Replies: 1
    Last Post: March 9th 2009, 02:14 AM

Search Tags


/mathhelpforum @mathhelpforum