GCD and LCM via groups and rings

Let a and b be integers. Consider the ring

G=\{ax+by:x,y\in\mathbb Z\}.

This is a well-ordered group. So by a result in this post it is infinite cyclic. We call the positive generator (a,b) the greatest common divisor (GCD) of a and b.

Consider now the ring

L=\{m\in\mathbb Z:m is divisible by both a and b\}.

It is also a well-ordered group. Hence it is generated by a single positive element [a,b], called the least common multiple (LCM) of a and b.


M_a=\{ax:x\in\mathbb Z\} and M_b=\{by:y\in\mathbb Z\}.

M_a, M_b and L are subings of G. Moreover, G=M_a+M_b and L=M_a\cap M_b. So by the Chinese remainder theorem,

G/L\cong G/M_a\times G/M_b,

which can be written as

(\mathbb Z/L)/(\mathbb Z/G)\cong(\mathbb Z/M_a)/(\mathbb Z/G)\times(\mathbb Z/M_b)/(\mathbb Z/G)

by the third isomorphism theorem. The groups in brackets are all finite groups of orders [a,b], (a,b), a and b. Hence [a,b]/(a,b)=ab/(a,b)^2, i.e.,


In general, let a_1,\dots,a_n\in\mathbb Z. As before, we can define

G=\{a_1x_1+\cdots+a_nx_n:x_i\in\mathbb Z\ \forall i\}

L=\{m\in\mathbb Z:m is divisible by a_i\ \forall i\}

M_i=\{a_ix:x\in\mathbb Z\} for i=1,\dots,n.

Then G=M_1+\cdots+M_n and L=M_1\cap\cdots\cap M_n. As before,



(*)\qquad\qquad\qquad (\mathbb Z/L)/(\mathbb Z/G)\cong\displaystyle\prod_{i=1}^n((\mathbb Z/M_i)/(\mathbb Z/G)).

So \displaystyle [a_1,\dots,a_n]/(a_1,\dots,a_n)=a_1\cdots a_n/(a_1,\dots,a_n)^n, i.e.

\boxed{a_1\cdots a_n=(a_1,\dots,a_n)^{n-1}[a_1,\dots,a_n]}.

If we replace \mathbb Z by \mathcal O_K for any number field K, then (*) takes the form

(\mathcal O_K/L)/(\mathcal O_K/G)\cong\displaystyle\prod_{i=1}^n((\mathcal O_K/M_i)/(\mathcal O_K/G)).

Taking cardinalities gives the following equation in terms of ideal norms



\boxed{N_{K/\mathbb Q}(a_1\cdots a_n)=N(G)^{n-1}N(L)}.


1 Comment

Filed under Algebra, Number theory

One response to “GCD and LCM via groups and rings

  1. Pingback: A bound on the multiplicative order | Samin Riasat's Blog

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s