Results 1 to 3 of 3

Math Help - prove

  1. #1
    Member
    Joined
    Feb 2008
    Posts
    125

    prove

    Prove that if d s a positive integer, d/a and d/b, then gcd(a,b)=d iff
    gcd(a/d,b/d)=1
    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 mandy123 View Post
    Prove that if d s a positive integer, d/a and d/b, then gcd(a,b)=d iff
    gcd(a/d,b/d)=1
    this is straightforward..

    ax + by = d \Longleftrightarrow (a/d)x + (b/d)y = 1 and a/d and b/d are both integers since d|a and d|b
    Follow Math Help Forum on Facebook and Google+

  3. #3
    MHF Contributor

    Joined
    Aug 2008
    From
    Paris, France
    Posts
    1,174
    Quote Originally Posted by kalagota View Post
    ax + by = d \Longleftrightarrow (a/d)x + (b/d)y = 1 and a/d and b/d are both integers since d|a and d|b
    The following addendum to kalagota's answer is probably obvious, but just in case: ax + by = d implies that \gcd(a,b)|d, so that \gcd(a,b)=d since conversely d|a and d|b imply d|\gcd(a,b).
    Follow Math Help Forum on Facebook and Google+

Similar Math Help Forum Discussions

  1. Prove a/b and a/c then a/ (3b-7c)
    Posted in the Discrete Math Forum
    Replies: 2
    Last Post: March 23rd 2010, 06:20 PM
  2. prove,,,
    Posted in the Number Theory Forum
    Replies: 1
    Last Post: March 1st 2010, 10:02 AM
  3. Prove |w + z| <= |w| +|z|
    Posted in the Algebra Forum
    Replies: 3
    Last Post: February 28th 2010, 06:44 AM
  4. Replies: 2
    Last Post: August 28th 2009, 03:59 AM
  5. How to prove that n^2 + n + 2 is even??
    Posted in the Algebra Forum
    Replies: 3
    Last Post: November 30th 2008, 02:24 PM

Search Tags


/mathhelpforum @mathhelpforum