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

2. ## Re: easy GCD question

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