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