# Monthly Archives: October 2015

## 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$.

Let

$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.,

$\boxed{ab=(a,b)[a,b]}$.

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,

$G/L\cong\displaystyle\prod_{i=1}^n(G/M_i)$,

i.e.,

$(*)\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

$N(L)/N(G)=\displaystyle\prod_{i=1}^n(N(M_i)/N(G))$.

Thus

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

1 Comment

Filed under Algebra, Number theory

## Products of consecutive integers dividing one another

I’ve been working on a project lately and I find myself stuck with the following problem.

Problem. Given positive integers $a, what can be said about the least positive integer $t$ such that $a(a+1)\cdots (a+t)$ does not divide $b(b-1)\cdots (b-t)$?

Obviously $t$ is bounded above by $b-a+1$ but this is very weak. Probably the least $t$ should be close to $b/a$.

Filed under Number theory

## A nice divisibility result on binomial coefficients

I just came across this cute little result on Quora and generalised it to the following.

Proposition. For any integers $0,

$\displaystyle\frac{n}{(n,k)}$ divides $\displaystyle\binom{n}{k}$.

First proof. Note that

$\displaystyle \frac{k}{(n,k)}\binom nk=\frac{n}{(n,k)}\binom{n-1}{k-1}$.

Since $\displaystyle\left(\frac{n}{(n,k)},\frac{k}{(n,k)}\right)=1$, the result follows. $\square$

Second proof. Let $n=p_1^{a_1}\cdots p_r^{a_r}$ and $k=p_1^{b_1}\cdots p_r^{b_r}$ where $p_1,\dots,p_r$ are the prime factors of $nk$. For each $i$, the base $p_i$ representations of $n$ and $k$ have $a_i$ and $b_i$ trailing zeros respectively. Hence by Kummer’s theorem $p_i^{\max\{a_i-b_i,0\}}$ divides $\displaystyle\binom nk$. Hence

$\displaystyle k\prod_{i=1}^rp_i^{\max\{a_i-b_i,0\}}=\prod_{i=1}^rp_i^{\max\{a_i,b_i\}}=[n,k]$

divides $\displaystyle k\binom nk$. Now the result follows using $[n,k]/k=n/(n,k)$. $\square$

A nice corollary is the following property of Pascal’s triangle.

Corollary. For any integers $0,

$\displaystyle\gcd\left(n,\binom nk\right)>1$.

Using the identity

$\displaystyle\binom nk\binom kr=\binom nr\binom{n-r}{k-r}$

the argument in the first proof above can be adapted to prove the following generalisation:

Proposition. For any integers $0\le r\le k\le n$,

$\displaystyle\frac{\binom nr}{\left(\binom nr,\binom kr\right)}$ divides $\displaystyle\binom{n}{k}$.

Corollary. Any two entries $\neq 1$ in a given row of Pascal’s triangle have a common factor $>1$.