Divisibility (gcd) 2

• Dec 16th 2008, 12:48 AM
Sea
Divisibility (gcd) 2
Show that: $b\neq 0$ and $a=bx+cy$ $\Rightarrow$ $(b,c)\mid (a,b)$
• Dec 16th 2008, 12:58 AM
o_O
Let $d_1 = (a,b)$. This implies $d_1 = {\color{red}a}m + bn$ for some $m,n \in \mathbb{Z}$

We're given that: ${\color{red}a} = bx+ cy$

So: $d_1 = ({\color{red}bx + cy})m + bn \ \Leftrightarrow \ d_1 = {\color{magenta} b}(xm+n) + {\color{magenta}c}ym$

Can you see why $(b,c) \mid d_1$ ?
• Dec 16th 2008, 01:21 AM
Sea
Yes...:) ... I can see...

$(b,c)=d \Rightarrow d|b$ and $d|c \Rightarrow d|b(xm+n)$ and $d|cym
\Rightarrow d|b(xm+n)+cym \Rightarrow d| d_1$

Thanks a million...