Results 1 to 2 of 2

Math Help - GCD Congruence problem

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

    GCD Congruence problem

    Prove that if gcd (a,b) = c, then bx congruences c (mod a) for some integer x.

    Proof.

    we have cx=a, cw=b, and ai+bj=c. I need a|bx-c for some x.

    bx-c = cwx-c = aw-c = aw - ai - bj

    now, how do I get an a out of the bj?
    Last edited by tttcomrader; February 7th 2008 at 06:32 PM.
    Follow Math Help Forum on Facebook and Google+

  2. #2
    MHF Contributor kalagota's Avatar
    Joined
    Oct 2007
    From
    Taguig City, Philippines
    Posts
    1,026
    Quote Originally Posted by tttcomrader View Post
    Prove that if gcd (a,b) = c, then bx congruences c (mod a) for some integer x.

    Proof.

    we have cx=a, cw=b, and ai+bj=c. I need a|bx-c for some x.

    bx-c = cwx-c = aw-c = aw - ai - bj

    now, how do I get an a out of the bj?
    let me try..

    (a,b) = c implies ay + bx = c for some integers y and x..
    now, bx - c = -ay = a(-y) for some integers y and x..
    and so, a|bx - c..
    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: March 9th 2009, 03:14 AM
  5. Congruence problem with LCM
    Posted in the Number Theory Forum
    Replies: 5
    Last Post: February 19th 2007, 01:55 PM

Search Tags


/mathhelpforum @mathhelpforum