If $c$ is a common divisor of $a$ and $b$ then $c$ divides the greatest common divisor of $a$ and $b$. What can we use to prove this?
Prove that if c is a common divisor of a and b then c divides the gcd of a and b..
4 Answers
Hint $\ $ By Bezout's identity, there are $\rm\:j,k\in\Bbb Z\:$ such that $\rm\:gcd(a,b)\, =\, j\:a + k\:b,\:$ which is clearly divisible by every common divisor of $\rm\:a,b.$
Thus a linear common divisor is always greatest, i.e. any common divisor $\rm\:d\:$ of $\rm\:a,b\:$ that is an integral linear combination of them $\rm\:d = j\:a + k\:b\:$ is necessarily the greatest common divisor, since, as above, every common divisor $\rm\:c\:$ divides $\rm\:d,\:$ hence $\rm\:c\le d.$
See here for a proof of Bezout's Identity and discussion of related matters.
-
0What is your definition for the greatest common divisor? – 2014-12-18
-
0@quid It works for both common gcd definitions, i.e. "greatest" means either wrt (absolute) value, or wrt divisibility, as in the *universal* definition $\ a\mid b,c\iff a\mid (b,c)\ \ $ – 2014-12-18
-
0Part of your answer is in fact wrong for the former (and for the former with parenthesis and the latter there is not really such a thing as *the* greatest common divisor, at least not if one want it to be an element). – 2014-12-18
-
0@quid I see nothing wrong. The former definition is intrinsic to Euclidean domains, and the latter to gcd domains. And the abuse of notation (uniqueness of the gcd up to unit factors) is ubiquitous. But this is very far from the question at hand. – 2014-12-18
-
0It is not ubiquitous; especially, at the elementary level it is quite common to insist that the gcd is positive (so that it is unique), and your initial comment is somewhat vague regrading this, too. With this definition your answer is wrong. You might want to be more explicit about your abuses of notation. – 2014-12-18
-
0@quid Not true. The proof works fine for that case, and the same idea works generally. If you still think something is wrong then please say *precisely* what that is and I will be happy to elaborate. – 2014-12-18
-
0It is false that each common divisor of the form $ja +kb$ is *the* gcd, as it could also be its negative. – 2014-12-18
-
0@quid But usually the elementary context treats *positive* integers, not $\,\Bbb Z.\,$ But even if it was $\,\Bbb Z,\,$ I cannot imagine anyone that would have a problem making the trivial extension to the above *Hint*. – 2014-12-18
-
0It is certainly up to you to consider the imprecisions in your answers as irrelevant or perhaps even pedagogic principles. I only thought you were actively searching my feedback on this post of yours, so I obliged. – 2014-12-18
-
0@quid It is almost universally true that my hints ignore inessential details in order to help focus on the essence of the matter. If you wish to provide an answer that emphasizes the above technicalities then please do so - I'll be happy to upvote it since I agree it is a point that any number theory student needs to understand (at some point). I have no idea what you mean about feedback. Today I have been going through all the "gcd" posts since I've been away the past few months, not anyone's feedback, e.g, see my recent activity. – 2014-12-18
-
0You seemed to try to draw my attention to this post via a comment linking to it placed at a peculiar place so that that I got notified. But perhaps this was an over-interpretation. – 2014-12-18
-
1@quid Ah, I see now. That comment was explicitly addressed to the OP, even though it was in the comments of your answer. Today has been so busy that now I don't recall why I placed the comment at that spot (maybe because I thought some readers of your answer might find the links helpful). Apologies for any confusion it may have caused. – 2014-12-18
First of all, it could be a definition. Otherwise, you may use the Euclidean algorithm and some elementary properties of division, or simply the unique prime factorisation of natural numbers.
-
0"First, of all it could be a definition." Really? What definition might that be. – 2012-09-26
-
1@user42362 E.g. the universal definition of gcd, viz. $\rm\:c\:|\:(a,b)\iff c\:|\:a,b\ \ $ – 2012-09-26
Use unique prime factorization: say $m=\displaystyle\prod_{i}{p_i}^{\alpha_i}$ and $n=\displaystyle\prod_i{p_i}^{\beta_i}$, then $\gcd(m,n)$ will contain the exponents $\min(\alpha_i,\beta_i)$.
Meanwhile, if $d$ has exponents $\delta_i$, then $d|m$ means exactly that each $\delta_i \le \alpha_i$. So, this is all a reformulation of the ($\delta_i\le\alpha_i$ and $\delta_i\le\beta_i$ then $\delta_i\le\min(\alpha_i,\beta_i)$) setting.
This can be shown based on what we are given by showing $a$ and $b$ in terms of a product of $c$. If $c$ is a common divisor of $a$ and $b$, that means a and b are each the product of at least one $c$ and another natural number: $a = c^np$ and $b=c^nq$, with $a,b,c,n,p,q \in \mathbb N$. There are then two possibilities:
- Either $c$, or a power of $c$ $c^n$, is the GCD of $a$ and $b$. Trivially, $c$ divides any $c^n$ where $n>0$.
- Neither $c$ nor any $c^n$ is the GCD of $a$ and $b$; in that case, $p$ and $q$ have their own GCD $m > 1$, and the GCD of $a$ and $b$ is $c^nm$; again, by inspection, we see that $c$ divides any $c^nm$ to produce $c^{n-1}m$.
-
0@Downvoter - anything to add or amend? – 2012-09-26