Let $R$ be a commutative ring with identity and $a_1, a_2, \dots,a_n \in R - \{0\}$. Then to find the gcd and lcm of $a_1, a_2, \dots,a_n$ and they exist in $R$ when $R$ is a UFD.

We can express $a_1, a_2, \dots,a_n$ uniquely as finite product of irreducible elements as:

$a_1 \sim p_1^{r_1}p_2^{r_2} \dots p_n^{r_n} $, $a_2 \sim p_1^{s_1}p_2^{s_2} \dots p_n^{s_n}$ , $\dots,$ $a_n \sim p_1^{t_1}p_2^{t_2} \dots p_n^{t_n}$

Now, we define:

$\gcd (a_1, a_2, \dots,a_n ) = p_1^{c_1}p_2^{c_2} \dots p_n^{c_n}$ where $c_i = \min\{r_i,s_i,...,t_i\}$ and,

$lcm(a_1, a_2, \dots,a_n ) = p_1^{d_1}p_2^{d_2} \dots p_n^{d_n}$ where $d_i = \max\{r_i,s_i,...,t_i\}$

I can intuitively define them but how can I prove that they exist in $R$?

Please Help!

  • 2
    $\begingroup$ Well, those formulas are in $R$ by definition, since $R$ is closed under multiplication and $p_i$ are in $R$. The real question you need to prove is, why are these the GCD and LCM. $\endgroup$ Mar 28, 2015 at 17:39
  • 2
    $\begingroup$ Incidentally, you might want to stick first with $n=2$ and then prove for general $n$ inductively, showing $\gcd(a_1,\dots a_n)=\gcd(\gcd(a_1,\cdots,a_{n-1}),a_n)$ and likewise for LCM. $\endgroup$ Mar 28, 2015 at 17:41
  • $\begingroup$ can you please help in showing that $\endgroup$
    – User8976
    Mar 28, 2015 at 18:15

1 Answer 1


By existence and uniqueness of prime factorizations, divisibility reduces to divisibility in each prime component, i.e. $\ p^{\large a} q^{\large a'}\!\cdots\mid p^{\large b} q^{\large b'}\!\cdots\!\iff p^{\large a}\mid p^{\large b},\,\ q^{\large a'}\!\mid q^{\large b'},\,\ldots\ $

So $\,\ a\mid b,c\iff p^{\large a}\mid p^{\large b},p^{\large c},\ \ q^{\large a'}\mid q^{\large b'},q^{\large c'},\ldots\ $ each which obey

$$\quad\ \ \ \ \ \ p^{\large a}\mid p^{\large b},p^{\large c}\! \iff a\le b,c \iff a\le \min\{b,c\} \iff p^{\large a}\mid p^{\large \min\{b,c\}}$$

$\!\begin{align}{\rm So}\ \ a\mid b,c&\iff p^{\large a}\mid p^{\large \min\{b,c\}},\ q^{\large a'}\mid q^{\large \min\{b',c'\}}\ldots\\[.5em] &\iff a\mid \color{#c00}{p^{\large \min\{b,c\}} q^{\large \min\{b',c'\}}}\ldots \end{align}$

Remark $\ $ Above we employ the universal characterization / definition of gcd and lcm, i.e.

$$\begin{align} a\mid b,c\iff a\mid \color{#c00}{\gcd(b,c)}\\ b,c\mid a\iff {\rm lcm}(b,c)\mid a\end{align}\qquad\qquad$$

The $ $ lcm $ $ case is just the dual $\, \ b,c\mid a\iff \cdots,\ $ by reversing divisiblities in the gcd proof.


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.