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$ – Thomas Andrews Mar 28 '15 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$ – Thomas Andrews Mar 28 '15 at 17:41
  • $\begingroup$ can you please help in showing that $\endgroup$ – User8976 Mar 28 '15 at 18:15

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 of the 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.