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

Question

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.

So, I had two ideas:

(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?

I'll appreciate any comments ;-)

Answer 1

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

Answer 2

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$