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

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?

• assuming the fundamental theorem of arithmetic ? or would you like to prove it too ? :-) and you'll need to use something like $\forall$, $\exists$ or a proof by induction or apply some theorem.. Apr 13, 2016 at 21:44
• You can see that $a$ is divisible by $d$ because all of the prime factors in $d$ appear in $a$, and the powers of those factors are less than those in $a$. So you will end up with $a/d = p_1^{\alpha_1 - min(\alpha_1,\beta_1)}\ldots p_t^{\alpha_t - \min(\alpha_t,\beta_t)} \in\mathbb{Z}$ Apr 13, 2016 at 21:54
• There isn't much to prove beyond definition. If p^n divides both a and b then p^n divides (a,b) so as p^min divides a and b p^min divides (a,b). If p^m doesn't divide both (or divides neither) then p^m doesn't divide (a,b) as p^greater than min doesn't divide both, the factorization is just the product of the min. It's almost by definition. But what I suggest you work on is the notation and indexing. p_1... p_s and p_1...p_t implies a has only the same prime factors as b. I'd say something to the effect of: ... to be continued. Apr 13, 2016 at 22:18
• ... cont. To be clearer that a and b's prime factors may differ, or may share to unknown degrees, I've say something like: "let p_1....p_t be the distinct prime factors of a and b (some p_i may be a factor of both a and be,, some of a only, and some of b only) so that a = $p_1^{a_1}...p_t^{a_t}$ (although some of the a_i might be 0 if that p_i is not a factor of a) and b=$p_1^{b_1}...p_t^{b_t}$ (ditto)" Apr 13, 2016 at 22:26

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!

• Okay let me know if this is correct: let $z | a$ and $z | b$ so $z$ is a common divisor of $a$ and $b$. $z$ must not divide $d$ to be the g.c.d. $z = \prod{p_i}^{\delta_i}$. So, $\frac{a}{z} = \frac{\prod p_i^{\alpha_i}}{\prod p_i^{\delta_i}}$ and $\frac{a}{z} = \frac{\prod p_i^{\beta_i}}{\prod p_i^{\delta_i}}$ so if $z$ were to be the g.c.d it should try to be as large as possible without being greater than $\alpha_i$ when dividing $a$ or $\beta_i$ when dividing $b$ so it should be the minimum of the two. That would make it equal to $d$. It makes sense now :D Apr 14, 2016 at 20:22

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

• I think you mean $\alpha_i > \beta_i$ since the above case covers when they're equal. Thank you though this is useful. Apr 14, 2016 at 19:09
• actually maybe not. The above case covers $\alpha_i < \beta_i$ Apr 14, 2016 at 19:12

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