Proof: Each common divisor c of a,b divides GCD(a,b)

there already exists a proof for this theorem: http://www.proofwiki.org/wiki/Common_Divisor_Divides_GCD

This one, however, uses Bêzout's Identity. I'm not allowed to use this for the proof.

(1) Use prime factorization (and here, I believe, I am not sure to use this, since it'll appear in later lesson - however, let's try this one as well!)

So let $a, b \in \mathbb{Z}$ non-negative. Let $a=\displaystyle\prod_{i}{p_i}^{\alpha_i}$ and $b=\displaystyle\prod_i{p_i}^{\beta_i}$, then $\gcd(a,b)$ will contain the exponents $\min(\alpha_i,\beta_i)$.

And what next?

(2) Let now $a,b \in \mathbb{Z}$ non-negative with $d = gcd(a,b)$. If now c is a common divisor of both a and b, I'll get:

$a = c^n \cdot p, b = c^n \cdot q$ for $p,q \in \mathbb{Z}, n \in \mathbb{N}$.

If $c$ or $c^n$ is the GCD, then it divides itself, which seems clear to me. If neither $c$ nor $c^n$ is the GCD, then.. ? Yes, what then?

(1) Next, consider any common divisor $c$, and make a note about how the exponents in its prime factorization compare to min$(\alpha_i, \beta_i)$.

(2) From here, consider what would happen if the greatest common divisor could not be written in the form $c^nr$. You can arrive at a contradiction by using the definition of gcd.

• (1)So for $c=\displaystyle\prod_{i}{p_i}^{c_i}$ the exponent $c_i \le min(\alpha_i , \beta_i)$ for any $i$ ? And since the GCD(a,b) contains all the prime numbers that c contains, this means c|d ? – Vazrael Mar 21 '14 at 20:50
• That's correct. You probably want to be a bit more precise in your language when you talk about numbers "containing" numbers, but you have exactly the correct idea. (You can be more precise in this way: Since min$(\alpha_i, \beta_i) - c_i$ is always non-negative, you can show explicitly that the result of the division will be an integer). – Jonny Lomond Mar 21 '14 at 20:58
• thank you very much! I know that I'm not always precise enough, I think it's due to my bad english language knowledge ;( One last question to way (2): If GCD(a,b) could not be written in the form $c^nr$, then.. I cannot conclude with a contradiction as you've mentioned above. I'd be glad if you can help me once more – Vazrael Mar 22 '14 at 11:01
• Actually I think the conclusion I had in mind would implicitly use the first proof. Better to stick with that one. – Jonny Lomond Mar 22 '14 at 21:22

Disclaimer:

What will follow, is similar to your first approach, however, it is formulated using slightly different words, to emphasize some parallels, which you might find helpful in the future.

Hint:

• There is an intuition which treats numbers as multisets or vectors where the coordinates are indexed by prime numbers and the values are the exponents in the factorization. For example, the prime factorization of $63 = 3\cdot3\cdot7$ would give you multiset $\{3\to2,7\to1\}$ (all the rest gets zero) or an infinite vector $(0,2,0,1,0,0,0,0,\ldots)$.
• With such an interpretation there are multiple parallels: $$\begin{array}{c|c|c} \textbf{operation} & \textbf{multiset analog} & \textbf{vector analog} \\\hline \text{multiplication} & \cup & + \\ \text{division} & \setminus & - \\ \text{divisibility} & \subseteq & \leq \\ \gcd & \cap & \min \end{array}$$
• What is important, the operators listed above treat the coordinates independently! That simplifies your problem to prove: $$c_p \leq a_p\ \ \land\ \ c_p \leq b_p\quad \implies\quad c_p \leq \min(a_p, b_p).$$

I hope this helps $\ddot\smile$