prove that prime factorization allows to give you the gcd of two numbers [duplicate]

I would like to prove that, given two integers:

$a = p_1^{\alpha_1}p_2^{\alpha_2}\cdots{p_t}^{\alpha_t}$

$b = p_1^{\beta_1} p_2^{\beta_2} \cdots p_s^{\beta_s}$

Then $\gcd(a,b)$ $=$ ${p_1}^{\min(\alpha_1, \beta_1)}{p_2}^{\min(\alpha_2, \beta_2)}\cdots {p_r}^{\min(\alpha_r\beta_r)}$

It is clear to me that

${p_1}^{\min(\alpha_1, \beta_1)}{p_2}^{\min(\alpha_2, \beta_2)}\cdots {p_r}^{\min(\alpha_r\beta_r)}$

is a divisor of both $a$ and $b$ but I can't manage to find a way to prove that it is the greatest of all the common divisors.

Solution 1:

If $c$ is a common divisor of $a$ and $b$, then $c=p_1^{\gamma_1}\cdots p_n^{\gamma_n}$, where we write $a=p_1^{\alpha_1}\cdots p_n^{\alpha_n}$ and $b=p_1^{\beta_1}\cdots p_n^{\beta_n}$ for some $n$.

Then $\gamma_i\leq \alpha_i$ and $\gamma_i\leq \beta_i$ for each $i$ and hence $\gamma_i\leq \min\{\alpha_i,\beta_i\}$ for each $i$. It follows that $c$ divides $p_1^{\min\{\alpha_1,\beta_1\}}\cdots p_n^{\min\{\alpha_n,\beta_n\}}$. Consequently, the latter is the gcd of $a,b$.