I have a proof question that I'm struggling on for my abstract algebra class.
Suppose that $a, b, c, d$ are integers with $a\neq 0$. Suppose that $a$ and $b$ are relatively prime. Part (i) If $d|a$ then, $b$ & $d$ are relatively prime.
I've started off the question: $$ d|a\Rightarrow a=kd$$ Also $$ax+by=1$$ Therefore $$kdx+by=1$$ Now I'm not sure if this is enough to say $d$ & $b$ are relatively prime however I doubt it. I'm not sure how I can get rid of the $k$ factor in my expression. This only shows that $kd$ and $b$ are relatively prime. Then there is Part (ii):
Prove that $gcd(a,c)=gcd(a,bc)$
Here I have said if $a|bc$ then the equation holds as since $$ax+by=1\Rightarrow acx+bcy=c$$ Therefore if $a|bc$ then $a$ divides both terms of $acx+bcy$ therefore $a|c$. Therefore $gcd(a,c)=gcd(a,bc)=a$ However I'm not sure how to show the result for $a\not|bc$. It's trvial for $c=1$. Anyway any help would be much appreciated.
Thanks
Best Answer
We give a proof of the type you were writing, but with the logical details made more explicit.
Theorem: (Bézout's Identity) Two integers $m$ and $n$ are relatively prime if and only if there exist integers $s$ and $t$ such that $ms+nt=1$.
Because $a$ and $b$ are relatively prime, there exist integers $x$ and $y$ such that $ax+by=1$.
Since $d\mid a$, there is an integer $k$ such that $a=dk$.
It follows that $d(kx)+by=1$. Thus (taking $s=kx$ and $t=y$) we conclude that $d$ and $b$ are relatively prime.
The second problem is more awkward if we want to use linear combinations, but it can be done that way. Since $a$ and $b$ are reatively prime, we have $ax+by=1$ for some integers $x$ and $y$.
Now consider linear combinations $as+ct$ of $a$ and $c$. We have $acx+bcy=c$, and therefore $$as+ct=as+(acx+bcy)t=a(s+cxt)+bc(yt).$$ Thus any linear combination of $a$ and $c$ is a linear combination of $a$ and $bc$.
The converse is obvious: any linear combination of $a$ and $bc$ is a linear combination of $a$ and $c$.
It follows that the set of linear combinations of $a$ and $c$ is the same as the set of linear combinations of $a$ and $bc$. Thus in each case the smallest positive linear combinations are the same, and hence the gcd's are the same.