Prove that if c is a common divisor of a and b then c divides the gcd of a and b..

Question

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?

Answer 1

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.

Answer 2

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.

Answer 3

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:

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

Answer 4

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.