# Greatest common denominator: $x\mid a$ and $x\mid b$ iff $x\mid\gcd(a,b)$

For $$a,b$$ in the natural numbers. How do I prove that $$x$$ divides $$a$$ and $$x$$ divides $$b$$ iff $$x$$ divides $$\gcd(a,b)$$.

$x|a$. let $a=a'x$. Let $d=\gcd (a,b)$. Let $a=Ad=a'x$. By unique factorization we can "break" this up to $a =(A)(d)=(A'x')(d'x")=(A'd')(x'x")=a'x$.

In other words $A'$ is a common factor of $A$ and $a'$, $x'$ is a common factor of $A$ and $x$, etc.

$x|b$. Let $b=b'x$. Let $b=Bd=b'x$.

So $b=B (d'x")=b'(x'x")$. By unique factoization, we can break this to: $b=(B'x')(d'x")=(b"d')(x'x")$.

Notice $d'x'x"=x'd$ is a common factor of $a$ and $b$.

But $d$ is the greatest common divisor. So $dx'\le d$ so $x' =1$ and $x"=x$ $A'=1$ and $B'=1$.

So $a=Ad=Ad'x$ and $b=Bd=d'x$ and $d =d'x$ and $x|d=\gcd (a,b)$

====

If $x|\gcd (a,b)$ and $\gcd (a,b)|a$ then $x|a$. As $\gcd (a,b)|b$, $x|b$.

You have to translate the word 'divide' into the language of ideals. We say that $a$ divides $b$ if $I_a \supset I_b$ (e.g. the set of multiples of $5$ contains the set of multiples of $15$). So for every common divisor $c$ of $a$ and $b$ we have $I_c \supset I_a$ and $I_c \supset I_b$ so that $I_c \supset I_a \cup I_b$. The smallest ideal that contains $I_a \cup I_b$ is $I_{\gcd(a,b)}$. This can be proved by using the property $I_{uv} = I_u \cup I_v$ and taking the intersection over all common factors of $a$ and $b$. Viewed like this what you have to prove is $I_x \supset I_a, I_x \supset I_b \iff I_x \supset I_{\gcd(a,b)}$.

Example $a = 30, b = 20$: $I_a = \{0, 30, 60, 90, \ldots\}$, $I_b = \{0, 20, 40, 60, \ldots\}$. Then $2$ and $5$ being the common divisors of $a$ and $b$ : $I_{\gcd(a,b)} = \{0, 2, 4, 6, 8, \ldots\} \cap \{0, 5, 10, 15, 20, \ldots\} = \{0, 10, 20, 30, 40, \ldots\}$. The proposition now sounds like $I_x \supset \{0, 30, 60, 90, \ldots\}, I_x \supset \{0, 20, 40, 60, \ldots\} \iff I_x \supset \{0, 10, 20, 30, 40, \ldots\}$.

Using fundamental theorem of arithmetic

$$\displaystyle a = \prod_{i=1}^{k}p_i^{\alpha_i} \,\, , \quad b = \prod_{i=1}^{k}p_i^{\beta_i}$$

We have : $$\displaystyle\gcd(a,b)=\prod_{i=1}^{k}p_i^{\min(\alpha_i, \beta_i)}$$

If $$x | a$$ and $$x | b$$ then $$x = \displaystyle \prod_{i=1}^{k}p_i^{\gamma_i}$$ , with $$\forall i \in \{1,2,\cdots,k\} \,\, : \,\, \gamma_i \leq \alpha_i \text{ and } \gamma_i \leq \beta_i$$

Then $$\forall i \in \{1,2,\cdots,k\} \,\, : \,\, \gamma_i \leq \min(\alpha_i, \beta_i)$$

Then $$x$$ devide $$\gcd(a, b)$$

And we have $$\gcd(a,b)$$ devide $$a$$ and $$b$$, then if $$x$$ devide $$\gcd(a,b)$$, $$x$$ will devide $$a$$ and $$b$$.

conclusion:

$$d = \gcd(a,b) \iff \left\{\begin{matrix}d | a \, \text{ and } \, d | b \\ x | a \, \text{et} \, x | b \implies x | d\end{matrix}\right.$$