# Relatively prime numbers and their gcd

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

• Write $x' = (kx)$. Don't look at it from Bézout's identity, look at it from the divisibility standpoint. If $g$ divides $d$, then it also divides $a$. – Daniel Fischer Jan 26 '14 at 19:49
• But then surely if I have $ax+by=1$ then $acx+bcy=c$. But then by writing $x'=cx$ & $y'=cy$ we get $ax+by=c$ which contradicts our assumption that $a$ & $b$ are relatively prime? – George1811 Jan 26 '14 at 19:54
• Forget about Bézout's identity. Well, don't; it's quite useful sometimes. But think in terms of divisibility when doing $\gcd$s, that's all in all more straightforward. However, you have $d\cdot (kx) + b\cdot y = 1$, which shows that $\gcd(d,y) \mid 1$. – Daniel Fischer Jan 26 '14 at 19:58
• Thanks it makes sense now. – George1811 Jan 26 '14 at 20:02

Think about what it means for $a$ and $b$ to be relatively prime: that they share no prime divisor, i.e. $p|a$ implies $p\not|b$ and $p|b$ implies $p\not|a$.

(i): Now suppose $d|a$ and that $p$ is a prime divisor of $d$. Then also $p|a$. Therefore $p$ does not divide $b$ ($a$ and $b$ are relatively prime). If on the other hand $p|b$ then $p\not|a$, therefore $p\not|d$ (since $d|a$). Thus $d$ and $a$ are relatively prime.

(ii): Let $e$ be a common divisor of $a$ and $bc$. Since $a$ and $b$ are relatively prime, $e|c$ (see (*) below). Therefore $e$ is a common divisor of $a$ and $c$. The other way goes the same. Thus the set of common divisors of $a$ and $c$ is equal to the set of common divisors of $a$ and $bc$. In particular, their greatest elements are equal, i.e. $\gcd(a,c)=\gcd(a,bc)$.

Edit:

(*) The argument implicitly contained here is as follows: Let $p$ be a prime divisor of $e$. Then $p$ divides $bc$. It needs to divide $b$ or $c$ (since it is prime). It cannot divide $b$, because $(a,b)=1$. So $p|c$. It follows that $e|c$.

• Thanks that makes a lot of sense. I tend to stray away from logic proofs sometimes, and try and achieve it through algebra. But that was very clear. Thank you – George1811 Jan 26 '14 at 20:00
• @George1811 You are welcome :-). – J.R. Jan 26 '14 at 20:05
• @George1811 Important point: for a correct and complete proof, one cannot, as above, simply claim that $\ (a,b)=1,\ e\mid \color{#c00}{a,bc}\Rightarrow\ e\mid c.\$ This is the crux of the matter. It requires rigorous *proof*. This can be proved by using the Bezout identity that you stated $\,\color{#c00}acx + \color{#c00}{bc}y = c,\,$ or by considering prime factorizations. – Bill Dubuque Jan 26 '14 at 20:24
• @BillDubuque The statement is completely trivial: Let $p$ be a prime divisor of $e$. Then $p$ divides $bc$. It needs to divide $b$ or $c$ (since it is prime). It cannot divide $b$, because $(a,b)=1$. So $p|c$. It follows $e|c$. Bezout's identity is not required. Nor is prime factorization. – J.R. Jan 26 '14 at 20:28
• @TooOldForMath As I said, one may use Bezout or prime factorizations (or various other properties equivalent to uniqueness of prime factorizations such as Euclid's Lemma) In any case, whichever one chooses, one does need to explicitly mention it to obtain a rigorous justification of the claim. Otherwise there is no way for a reader to judge if the proof is correct and complete. Before Gauss (and even after) many incorrect proofs of related results were given because it was never realized that prime factorizations could possibly be nonunique. If so, such results generally fail. – Bill Dubuque Jan 26 '14 at 20:43

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.

• I had the same issue with the identity in some of the comments above. If we have $ax+by=1$ then $acx+bcy=c$ then taking $s=cx$ & $t=cy$ we achieve $as+bt=c$ which is clearly false. – George1811 Jan 26 '14 at 20:10
• I have written out the argument for $\gcd(a,c)=\gcd(a,bc)$ using linear combinations. It is not my favourite way to do it, but it shows that the idea of linear combinations can be used for the second problem also. – André Nicolas Jan 26 '14 at 20:49