# Math Help - easy GCD question

1. ## 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.

2. ## Re: easy GCD question

Originally Posted by dwsmith
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.