# Proof verification of GCD prime factorization

This is a classical property of $$\gcd$$ but I din't find a proof as mine, so I don't know if this is duplicate. (If there's a simpler proof let me know, please).

The statement is:

Let $$a,b >1$$ integers and suppose that their respective prime factorizations in powers of primes are

$$a=p_1 ^{\alpha_1} \cdots p_r ^{\alpha_r},$$ $$b=p_1 ^{\beta_1} \cdots p_r ^{\beta_r},$$

where $$\alpha_i, \beta_i \geq 0.$$

Prove that $$\gcd(a,b)=p_1 ^{\min \{ \alpha_1, \beta_1 \} } \cdots p_r ^{\min \{ \alpha_r, \beta_r \} }.$$

My attempt:

Let $$d=p_1 ^{\min \{ \alpha_1, \beta_1 \} } \cdots p_r ^{\min \{ \alpha_r, \beta_r \} }.$$ Observe that for all $$i \in \{1,...,r \}$$, we have $$p_i^{\min \{ \alpha_i, \beta_i \} } \mid p_i^{\alpha_i}$$ (easy to prove). Then, by divisibility properties: $$p_1 ^{\min \{ \alpha_1, \beta_1 \} } \cdots p_r ^{\min \{ \alpha_r, \beta_r \} } \mid p_1 ^{\alpha_1} \cdots p_r ^{\alpha_r}.$$ i.e., $$d \mid a$$.

Similarly, $$d \mid b$$.

Now, consider the numbers $$a'=p_1^{\alpha_1 - \min \{ \alpha_1, \beta_1 \} } \cdots p_r^{\alpha_r - \min \{ \alpha_r, \beta_r \} }$$ and $$b'=p_1^{\beta_1 - \min \{ \alpha_1, \beta_1 \} } \cdots p_r^{\beta_r - \min \{ \alpha_r, \beta_r \} }.$$

Let $$d'$$ a prime common divisor of $$a'$$ and $$b'$$.

In one hand, we have that $$d' \mid a' \iff d' \mid p_1^{\alpha_1 - \min \{ \alpha_1, \beta_1 \} } \cdots p_r^{\alpha_r - \min \{ \alpha_r, \beta_r \} }.$$ Since $$d'$$ is a prime number, $$d' \mid p_j^{\alpha_j - \min \{ \alpha_j, \beta_j \} }$$ for some $$j$$. Then, $$\alpha_j - \min \{ \alpha_j, \beta_j \}>0,$$, hence, $$\min \{ \alpha_j, \beta_j \}= \beta_j.$$ Observe that $$d' \mid p_j,$$ and then, $$d'=p_j$$.

In the other hand, $$p_j^{\beta_j - \min \{ \alpha_j, \beta_j \}}=1.$$ Therefore, $$p_j \nmid b'$$, since $$p_j$$ is not a prime factor of $$b'$$.

We clonclude that $$a', b'$$ have not common prime divisors, and then, $$\gcd (a', b')=1$$.

There exists $$x,y \in \mathbb{Z}$$ such that $$a'x+b'y=1 \hspace{1cm} (1)$$

Note that $$a=da', b=db',$$ then, by the equation $$(1), ax+by=d.$$

Then, $$d \mid a, d \mid b,$$ and $$d$$ is a linear combination of $$a$$ and $$b$$, so $$d$$ must be $$\gcd (a,b)$$

• It's classical. – Michael Rozenberg Aug 11 '19 at 5:48

There are various ways to prove that a common divisor $$d$$ of $$\,a,b\,$$ is greatest. Your proof fully repeats a common Bezout based proof of the direction $$(\Leftarrow)$$ of
$$d = \gcd(a,b)\,\iff\, d\mid a,b\ \ \,\&\ \gcd(a/d,b/d) = 1\qquad$$