Why must all common factors of x and y also be factors of gcd(x,y)?

Question

I have found a pretty convoluted proof for this phenomenon, but I cannot figure out an intuitive explanation, so that is what I am looking for.

@lulu yes; my proof for this was basically that we can get to the gcd using a linear combination of x and y, and a linear combination of x and y must be divisible by all of the shared factors of x and y thus the gcd must be divisible by all the shared factors of x and y. But I wish I could have a more direct way to think about this. — notReallyDev, Aug 05 '17 at 20:56
The name $\gcd$ stands for greatest common divisor, so the intuition is that $\gcd(x,y)$ is the common divisor of $x$ and $y$ which is a multiple of any common divisor of those numbers. Did you instead mean that you want a proof that a $\gcd$ exists? — hardmath, Aug 05 '17 at 20:56
@hardmath there are some factors of x and y which may not be divisible by one another, for example 2 and 3 for x=6 and y=12. But both 2 and 3 are divisible by the gcd 6. Why is this always the case? — notReallyDev, Aug 05 '17 at 21:00
@hardmath $\gcd(x,y)$ is the common divisor which is largest. The fact that it is a multiple of all common divisors is a happy coincidence, a theorem and a very usable fact. But it is not part of the definition. — Arthur, Aug 05 '17 at 21:02
It is not true in every ring, but in a ring where it is true we call that ring a gcd ring. The integers $\mathbb{Z}$ are an example of a gcd ring, as indeed is every principle ideal domain. — hardmath, Aug 05 '17 at 21:02
Your question is a good one. I don't think it is a trivial point at all. It is, of course, obvious from unique factorization, and it follows from Bezout's Lemma as I mentioned. But neither of those arguments are easy. You are correct to think it is un-intuitive. — lulu, Aug 05 '17 at 21:05

score 3 · Answer 1 · answered Aug 05 '17 at 21:24

It depends on your definition of greatest common divisor.

If you define $\gcd(a,b)$ as the largest member of the set of common divisors, then it's indeed not obvious that, if $z$ is a common divisor of $x$ and $y$, then $z$ divides $\gcd(x,y)$.

However, the greatest common divisor $d=\gcd(x,y)$ can be written as $d=rx+sy$, for some integers $r$ and $s$ (this is known as Bézout's identity). Suppose $x=az$ and $y=bz$. Then $$ d=rx+sy=arz+bsz=(ar+bs)z $$ so $z$ indeed divides $d$.

See Henno Brandsma's answer for the case when a different definition is used.

score 1 · Answer 2 · answered Aug 05 '17 at 21:08

1

A greatest common divisor of $x$, $y$ is by definition a number $z$ that satisfies:

$z | x$ and $z | y$ (where $|$ denotes (evenly) divides) (it's a common divisor)
If $r$ is any number with $r| x$ and $r | y$ then $r|z$ (it's the greatest common divisor, where "greatest" is measured in the partial order $|$).

It is unique up to sign in $\mathbb{Z}$. The property you're looking for is property 2. which is part of the definition. So nothing to prove.

answered Aug 05 '17 at 21:08

Henno Brandsma

242,131

Nothing in what you wrote suggests that if $n,|,x,y$ then $n,|,\gcd(x,y)$. – lulu Aug 05 '17 at 21:11
@lulu Yes, 2 says exactly that (note that $z = \gcd(x,y)$.) – Henno Brandsma Aug 05 '17 at 21:14
@lulu : Read again part 2 of Henno's definition. $z$ there is $\gcd(x,y)$. – hardmath Aug 05 '17 at 21:15
1

Ha! Fair enough. But that is obviously not the ordinary definition of greatest common divisor. That phrase clearly refers to "the largest number $d$ such that $d$ divides both of $x,y$." – lulu Aug 05 '17 at 21:16
@hardmath one first defines it, then show uniqueness up to sign.. Calling it $\gcd(x,y)$ already suggest we already have uniqueness. I was taught that it is the positive one (in the integers) – Henno Brandsma Aug 05 '17 at 21:16
@lulu it is the mathermatical definition of greatest common divisor, namely the supremum of ${x,y}$ in the partial order $(\mathbb{Z}, |)$. – Henno Brandsma Aug 05 '17 at 21:18
Team, I think it is 100% clear that the definition the OP intends is the ordinary one. For $x,y\in \mathbb N$ $\gcd (x,y)$ is the largest positive number which divides both of $x,y$. – lulu Aug 05 '17 at 21:18
@lulu It works in any ring. not just the ordered set of integers. – Henno Brandsma Aug 05 '17 at 21:19
What works in any ring? You have to show that your notion is equivalent to the standard notion. That is simply not trivial. – lulu Aug 05 '17 at 21:20
Right, I'm not disputing your definition. See my Comment above, and compare the definition given in Wikipedia for commutative rings generally. There is no notion of order among ring elements to rely on, so the partial order induced by divisibility is the natural criterion. Here we are required to consider associate classes where two ring elements are equivalent if one is a unit times the other. – hardmath Aug 05 '17 at 21:21
My point is trivial, yet (I think) valid. The OP is asking about the common English notion of gcd. Under that definition they are asking about a real theorem. – lulu Aug 05 '17 at 21:22
@lulu The definition taught in elementary school is not the one used in mathematics. Just as some people thing $1$ is a prime. You can define division in any ring ($a|b$ iff there is some $c$ such that $ac= b$ etc.) so the notion of a $\gcd$ of two (or more) elements makes sense in any ring, not just the integers, if you use "my" definition. – Henno Brandsma Aug 05 '17 at 21:24
Ok. Ask the OP which definition they intended. – lulu Aug 05 '17 at 21:25
Hi, wow. This escalated quickly and a lot of this is out of the scope of my knowledge (rings??) but yes, I did not include property 2 in my definition of gcd; I was asking whether or not it held true given that it is the largest number satisfying property 1. – notReallyDev Aug 05 '17 at 21:29
@Michelle Oh, no worries. We are debating a side issue. I think your question is clear. – lulu Aug 05 '17 at 21:31
@lulu In any ring, if $,c\mid a,b\iff c\mid d,$ then $d$ is called a gcd of $,a,b.,$ Thus $,c\mid a,b\iff c\mid \gcd(a,b),,$ where the gcd is defined only up to associates. I do agree with your objection, since it is highly unlikely the the OP is using this general definition. Indeed, the point of the exercise is to prove that the classical definition is equivalent to this general definition. – Bill Dubuque Aug 05 '17 at 21:54
@BillDubuque entirely agreed. – lulu Aug 05 '17 at 22:11

score 0 · Answer 3 · answered Aug 05 '17 at 22:50

(Note: this is not intended as a proof, since OP has already proved the given theorem using Bézout's identity.)

If there are two common factors $a$ and $b$ of $x$ and $y$, then the least common multiple of $a$ and $b$ is also a common factor. The least common multiple is larger unless one of $a$ and $b$ is a multiple of the other. In other words, the greatest common factor is the least common multiple of all the common factors.

It also may help to think in terms of prime factorizations. If we think of divisibility in terms of primes, then $a$ is a factor of $x$ if and only if for each prime $p$, the power of $p$ in $a$ is less than or equal the power of $p$ in $x$ (possibly $0$ if $p$ is not a factor of $x$). For example, suppose there are three primes in play, $p$, $q$, and $r$ with $x = p^2q^5r$ and $y = p^3q^3r^3$. Applying this notion of divisibility, we get that common factors are precisely numbers of the form $p^iq^jr^k$ with $0 \leq i \leq 2$, $0 \leq j \leq 3$, and $0 \leq k \leq 1$. The greatest common factor is then $p^2q^3r$, and any other common factor is a factor of this greatest factor.

score 0 · Answer 4 · answered Aug 05 '17 at 22:59

A slight restatement by contradiction:

Assume that integers $a,b$ has a common divisor $q$ that is not a factor of $\gcd(a,b)$.

Then in the prime factorisations, $q$ has a prime factor that is a higher power than that in the $\gcd(a,b)$.

Let that prime factor be $p$, then $p\cdot \gcd(a,b)$ is also a common divisor of $a,b$.

But $p \cdot \gcd(a,b)> \gcd(a,b)$, which is a contradiction that the $\gcd(a,b)$ is the greatest common divisor.

Why must all common factors of x and y also be factors of gcd(x,y)?

4 Answers4