Results 1 to 2 of 2

Math Help - easy GCD question

  1. #1
    MHF Contributor
    Joined
    Mar 2010
    From
    Florida
    Posts
    3,093
    Thanks
    5

    easy GCD question

    if gcd(a,r) = d and gcd(b,r) = 1, then gcd(ab,r) = d.

    d|a, \ d|r, \ 1|b, \ 1|r

    By multiplying, we have d|ab and we are giving d|r.

    So d is a divisor of ab and r. How can I show d is the greatest?

    I tried contradiction assuming c = gcd(ab,r) but not sure where to go with that.
    Follow Math Help Forum on Facebook and Google+

  2. #2
    Member Haven's Avatar
    Joined
    Jul 2009
    Posts
    197
    Thanks
    8

    Re: easy GCD question

    Quote Originally Posted by dwsmith View Post
    if gcd(a,r) = d and gcd(b,r) = 1, then gcd(ab,r) = d.

    d|a, \ d|r, \ 1|b, \ 1|r

    By multiplying, we have d|ab and we are giving d|r.

    So d is a divisor of ab and r. How can I show d is the greatest?

    I tried contradiction assuming c = gcd(ab,r) but not sure where to go with that.
    Alright Let's assume c=gcd(ab,r) where c>d.

    So, we have that c|ab and c|r.

    Note that we must have that gcd(b,c)=1 since gcd(b,r)=1 and c|r.

    Therefore, it follows that c|a. So we have that c|a, c|r but c>d=gcd(a,r). Which is a contradiction.
    Follow Math Help Forum on Facebook and Google+

Similar Math Help Forum Discussions

  1. an easy question
    Posted in the Math Software Forum
    Replies: 2
    Last Post: March 14th 2010, 08:13 AM
  2. very easy question!
    Posted in the Statistics Forum
    Replies: 7
    Last Post: January 25th 2010, 03:01 PM
  3. Seemingly easy question... too easy.
    Posted in the Pre-Calculus Forum
    Replies: 3
    Last Post: August 23rd 2009, 09:36 PM
  4. easy, easy question
    Posted in the Discrete Math Forum
    Replies: 3
    Last Post: July 14th 2009, 07:38 AM
  5. Easy question
    Posted in the Algebra Forum
    Replies: 3
    Last Post: July 1st 2007, 05:52 PM

/mathhelpforum @mathhelpforum