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)}.

Advertisements

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

Leave a comment

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<k\le n,

\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<k<n,

\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.

Leave a comment

Filed under Number theory