# Proving this corollary of the Unique Factorization Theorem (of Integers)…

Here's the Corollary in it's entirety

Corollary 1.3.5 (from Numbers, Groups, and Codes by J.F. Humphreys)

Let $a,b \in \mathbb{Z^+}$ and let $$a=\prod_{i=1}^r p_i^{n_i}$$ $$b=\prod_{i=1}^r p_i^{m_i}$$ be the prime factorizations of $a,b$ where $p_1,\ldots,p_n$ are distinct primes and $n_1,\ldots,n_r,m_1,\ldots,m_r\in \mathbb{N}$. Then the $\gcd(a,b)=d$ is given by $$d=\prod_{i=1}^r p_i^{k_i}$$ where $k_i=\min(n_i,m_i)$ $\forall i$ and the $\mathbb{lcm}(a,b)=f$ is given by $$f=\prod_{i=1}^r p_i^{\beta_i}$$ where $\beta_i=\max(n_i,m_i)$ $\forall i$.

Alright so here is what I'm thinking in regards to proving this (it's meager I warn you), I just know idea if it's rigorous enough:

Attempt at a Proof

We know that $a=\prod_{i=1}^r p_i^{n_i}$ and $b=\prod_{i=1}^r p_i^{m_i}$. Consider $d\in \mathbb{Z^+}$ s.t $\gcd(a,b)=d$. Then how do we write $d$ as a prime factorization? Well we know that $d$ divides $\prod_{i=1}^r p_i^{n_i}$, so we know by another theorem that $d$ must divide at least one of the primes in this product. Similar reasoning follows for $b$.

So basically, all I've been able to do is state the givens. I think I somehow need to get to the fact that $k_i$ will be the $\min(n_i,m_i)$. I've really no idea where to progress. I would very much like to figure this out and the book does not give a proof. Once I can figure out the $\gcd$ I think I will have no trouble with the $\mathbb{lcm}$. If anyone could lead me down the right track, I'd be very thankful!

• Hint: You have a good suspicion of what $d$ should be ($k_i=\text{min}(n_i,m_i)$). Now just verify that this number satisfies the properties of the gcd. So show that it divides $a$ and $b$, and then show that any common divisor of $a$ and $b$ divides $d.$ – Ragib Zaman Jul 18 '14 at 19:59
• As Ragib says, simply show that $\prod p^{\min}$ and $\prod p^\max$ satisfy the universal properties of gcd and lcm. (Namely, $x\mid a,b\Leftrightarrow x\mid \gcd(a,b)$ and $a,b\mid y\Leftrightarrow {\rm lcm}(a,b)\mid y$.) Strangely your corollary never actually says what $d$ and $f$ are (and even the inequalities it gives are incorrect, they should be $\le$ not $<$)! – blue Jul 18 '14 at 20:01

Let $$d= \prod_{i=1}^r p_i^{k_i}.$$ Then $$d\cdot\prod_{i=1}^r p_i^{m_i-k_i} = \prod_{i=1}^r p_i^{m_i} = a,$$ so $d$ is indeed a divisor of $a$. Similarly we can show that $d$ is a divisor of $b$. So $d$ is a common divisor of $a$ and $b$.
It remains to show only that there is no larger common divisor. If $\ell_i>k_i$ for at least one value of $i$, then either $\ell_i>m_i$ or $\ell_i>n_i$. Suppose the former. Then $$d<\prod_{i=1}^r p_i^{\ell_i}.$$ This product cannot be a divisor of $b$, because $$\frac{b}{\prod_{i=1}^r p_i^{\ell_i}} = \frac{\cdots p_i^{m_i} \cdots}{\cdots p_i^{\ell_i} \cdots}$$ and when we reduce to lowest terms we're left with a factor of $p_i$ in the denominator. Hence this product is not a common divisor of $a$ and $b$.
The only other hope of finding a common divisor of $a$ and $b$ that's bigger than $d$ would be a number not of the form $\prod_{i=1}^r p_i^{\ell_i}$. But that would be a divisor of $a$ whose prime factors include some number other than $p_1,\ldots,p_r$. That is ruled out by uniqueness of prime factorizations.
Hint $\$ If $\ p\nmid a,b\$ then $\ (p^m a, p^n b)\, =\, p^{\min(m,n)} (a,b).\$ Recurse on $\,(a,b).$
Proof  wlog $\,m = \min(m,n)\,$ so $\,(p^ma,p^nb) = p^m(\color{#c00}{a,p^{n-m}}b) = p^m(a,b)\,$ by Euclid's Lemma,
because,  by  hypothesis, $\,\ (a,p)=1,\$ therefore, $\,\ (\color{#c00}{a,p^{n-m}})=1,\$ again,  by Euclid's Lemma.