Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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?

share|improve this question
add comment

4 Answers 4

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.

share|improve this answer
    
"First, of all it could be a definition." Really? What definition might that be. –  debitanostra Sep 26 '12 at 10:32
1  
@user42362 E.g. the universal definition of gcd, viz. $\rm\:c\:|\:(a,b)\iff c\:|\:a,b\ \ $ –  Bill Dubuque Sep 26 '12 at 16:26
add comment

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.

share|improve this answer
add comment

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.

share|improve this answer
add comment

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$.
share|improve this answer
    
@Downvoter - anything to add or amend? –  KeithS Sep 26 '12 at 17:31
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.