Results 1 to 2 of 2

Thread: easy GCD question

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

    easy GCD question

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

    $\displaystyle 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 $\displaystyle 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 $\displaystyle gcd(a,r) = d$ and $\displaystyle gcd(b,r) = 1$, then $\displaystyle gcd(ab,r) = d$.

    $\displaystyle 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 $\displaystyle c = gcd(ab,r)$ but not sure where to go with that.
    Alright Let's assume $\displaystyle c=gcd(ab,r)$ where $\displaystyle c>d$.

    So, we have that $\displaystyle c|ab$ and $\displaystyle c|r$.

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

    Therefore, it follows that $\displaystyle c|a$. So we have that $\displaystyle c|a$, $\displaystyle c|r$ but $\displaystyle 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: Mar 14th 2010, 08:13 AM
  2. very easy question!
    Posted in the Statistics Forum
    Replies: 7
    Last Post: Jan 25th 2010, 03:01 PM
  3. Seemingly easy question... too easy.
    Posted in the Pre-Calculus Forum
    Replies: 3
    Last Post: Aug 23rd 2009, 09:36 PM
  4. easy, easy question
    Posted in the Discrete Math Forum
    Replies: 3
    Last Post: Jul 14th 2009, 07:38 AM
  5. Easy question
    Posted in the Algebra Forum
    Replies: 3
    Last Post: Jul 1st 2007, 05:52 PM

/mathhelpforum @mathhelpforum