3

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

George1811
  • 1,981
  • 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

2 Answers2

3

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.

André Nicolas
  • 507,029
  • 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
2

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$.

J.R.
  • 17,904
  • 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
  • @TooOldForMath The argument you sketched uses the existence of a prime factor $p$ of $e$, and the prime divisor property $\ p\mid xy\mid p\mid x,$ or $,p\mid y$. This property is easily seen to be equivalent to the uniqueness of prime factorizations. So you've essentially used the existence and uniqueness of prime factorizations, i.e. the Fundamental Theorem of Arithmetic (FTA) This is not "completely trivial". One of the goals of an elementary number theory course is to (rigorously!) teach what follows from FTA (and what does not!). – Bill Dubuque Jan 26 '14 at 20:49
  • @BillDubuque Yes, I agree with you. Thank you for your criticism, I have edited the answer accordingly. – J.R. Jan 26 '14 at 20:54
  • @TooOldForMath Great! This may seem a bit pedantic at this level, but as soon as one studies factorization in more general numbers systems, e.q. quadratic integers such as $a+b\sqrt{n}$ then one faces the difficulty that factorizations generally are not unique, so it is essential to know which results depend crucially on uniqueness, and which do not. Even great mathematicians made errors overlooking such subtleties (e.g. Kummer's attempted proof of Fermat's Last Theorem). – Bill Dubuque Jan 26 '14 at 20:57
  • @BillDubuque: Completely agreed. The devil is, as always, in the detail. – J.R. Jan 26 '14 at 21:02
  • Indeed, esp. for matters like this where we have such strong empirical (vs. logical) intuition. Our empirical intuition on integer arithmetic is stronger than most other fields of math. So empirical inferences may obstruct logical inference. Every prime factorization we've seen is unique. Some think that it is "obviously" always true, i.e. that no proof is required. Until Gauss (Disq. Arith, 1801), no one realized that this requires rigorous proof. Once more general numbers were studied the gaps became evident, e.g. see this answer for a failure of Euclid's Lemma. – Bill Dubuque Jan 26 '14 at 21:20