Proof verification of GCD prime factorization

Question

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)$

Answer 1

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$$

Another more general proof of the above follows immediately from the basic GCD Distributive Law.

You won't typically see the proof in your question presented that way since normally one invokes the above theorem by name instead of proving it on the fly within another proof (this basic theorem is widely invoked so it deserves to be abstracted out and named to permit easy reuse).