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!

  • $\begingroup$ 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.$ $\endgroup$ – Ragib Zaman Jul 18 '14 at 19:59
  • $\begingroup$ 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 $<$)! $\endgroup$ – 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.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.