0
$\begingroup$

enter image description here

I think the strategy for this problem would be i assume some arbitrary element is in gcd(a,b) and chase it into the rhs and then do it the other way around , but i am not sure how to even start this one.

$\endgroup$
  • $\begingroup$ Use the fact that $\gcd(u,v)$ is the smallest positive number in $\{ux+vy:x,y\in\mathbb Z\}$. $\endgroup$ – Dave Feb 18 '19 at 21:43
  • $\begingroup$ so would i have gcd(a,b)=ax+by=ax/d+by/d=dgcd(a/d,b/d)? how would the other direction go? $\endgroup$ – H.B Feb 21 '19 at 6:51
0
$\begingroup$

We can rephrase the conditions as $a=p\cdot d$ and $b=q\cdot d$ with $p,q\in\mathbb{N}$.

Then $$\gcd(a,b)=\gcd(pd,qd)=d\cdot\gcd(p,q)=d\cdot\gcd(\frac{a}{d},\frac{b}{d})$$

| cite | improve this answer | |
$\endgroup$
  • 1
    $\begingroup$ Yes but the second equality is really what the OP is trying to prove. $\endgroup$ – Dave Feb 18 '19 at 21:47

Not the answer you're looking for? Browse other questions tagged or ask your own question.