How to prove that the g.c.d is equal to the prime factorization raised to the minimum of two powers

Question

for the prime factorization of $a$ and $b$ as $$a = p_1^{\alpha_1}p_2^{\alpha_2}\cdots{p_t}^{\alpha_t}$$ and $$b = p_1^{\beta_1} p_2^{\beta_2} \cdots p_s^{\beta_s}.$$ I want to prove that $d = gcd(a,b)$ is equal to $${p_1}^{\min(\alpha_1, \beta_1)}{p_2}^{\min(\alpha_2, \beta_2)}\cdots {p_r}^{\min(\alpha_r\beta_r)}$$ so I begin by proving that $d$ is a common divisor of $a$ and $b$.

$$\frac{a}{d} = \frac{p_1^{\alpha_1} p_2^{\alpha_2} \cdots p_t^{\alpha_t}}{p_1^{\min(\alpha_1\beta_1)}p_2^{\min(\alpha_2\beta_2)} \cdots {p_s}^{\min(\alpha_s\beta_s)}}$$ and

$$\frac{b}{d} = \frac{p_1^{\beta_1}p_2^{\beta_2} \cdots p_s^{\beta_s}}{p_1^{\min(\alpha_1\beta_1)}{p_2}^{\min(\alpha_2\beta_2)} \cdots p_s^{\min(\alpha_s\beta_s)}}$$

I don't know if $a$ is always divisible by $d$ in $\mathbb{Z^+}$ I'm also very new to proofs can I have some guidance?

Answer 1

Remember what divisibility means: $d$ divides $a$ if I can find some integer $c$ such that $dc = a$.

Let's look at one term of your $\frac{a}{d}$ fraction: $\frac{p_1^{\alpha_1}}{p_1^{min(\alpha_1, \beta_1)}}$.

Since $min(\alpha_1, \beta_1) \le \alpha_1$, this fraction has an integer value of $p_1^{\alpha_1 - min(\alpha_1, \beta_1)}$

You can then do this for every prime $p$ in your expansions of both $\frac{a}{d}$ and $\frac{b}{d}$

You're not quite done, though: you've only shown that $d$ is a common divisor of $a$ and $b$ after you're done with these steps. You still need to show that it's the greatest common divisor: this is true if a common divisor of $a$ and $b$, call it $z$, divides $d$. If every common divisor divides $d$ then you can be sure that $d$ is your greatest common divisor. I'll leave this step to you.

Let me know in a comment if you have any questions!

Answer 2

In $a / d$ you have factors $$ F_i = \frac{p_i^{\alpha_i}}{p_i^{\min(\alpha_i, \beta_i)}} $$ and two cases:

1. $\min(\alpha_i, \beta_i) = \alpha_i$ then $F_i = 1$ and
2. $\min(\alpha_i, \beta_i) = \beta_i$ then $\alpha_i \ge \beta_i$ and $\alpha_i - \beta_i \ge 0$ so $F_i = p_i^{\alpha_i - \beta_i} \in \mathbb{Z}$.

This gives $F_i \in \mathbb{Z}$ and for the product $a/d \in \mathbb{Z}$. A similar argument yields $b/d \in \mathbb{Z}$ and we see that $d$ is a common divisor of $a$ and $b$.

Answer 3

You have the right idea but perhaps a nicer way to put it would the this.

The $\gcd(a,b)$ has a prime factorization. Let $p$ be a prime factor of $gcd(a,b)$. Then $p$ is a prime factor of both $a$ and $b$. So if we write the prime factor of $\gcd(a,b)$ as $\gcd(a,b) = \prod p_i^{c_i}$ then we can write the prime factor of $a$ as $a = \prod q_k^{d_k} \prod p_i^{\alpha_i}$ where $p_i|\gcd(a,b)$ (i.e. $p_i$ divides both $a$ and $b$) and $q_k$ does not (ie. $q_k$ divides $a$ but not $b$). And likewise we can write the prime factor of $b$ as $b = \prod r_k^{e_k}\prod p_i^{\beta_i}$ (where $r_k$ divides $b$ but not $a$ and $p_i$ divides both $a$ and $b$).

Okay... so $\gcd(a,b)|a$ so each $p_i^{c_i}|a$ so $c_i \le \alpha_i$ and likewise $p_i^{c_i}|b$ so $c_i \le \beta_i$ so $c_i \le \min(\alpha_i, \beta_i)$.

But $\min(\alpha_i, \beta_i)\le \alpha_i$ so $p^{\min(\alpha_i, \beta_i)}$ divides $p^{\alpha_i}$ which divides $a$ so $p^{\min(\alpha_i, \beta_i)}$ divides $a$. And likewise $\min(\alpha_i, \beta_i)\le \beta_i$ so $p^{\min(\alpha_i, \beta_i)}$ divides $p^{\beta_i}$ which divides $b$ so $p^{\min(\alpha_i, \beta_i)}$ divides $b$. So $p^{\min(\alpha_i, \beta_i)}|\gcd(a,b)$.

So $\min(\alpha_i, \beta_i) \le c_i$.

So $c_i = \min(\alpha_i, \beta_i)$ and $\gcd(a,b) = \prod p_i^{\min(\alpha_i,\beta_i)}$.