1
$\begingroup$

How is it true that:

If $a_1, a_2,\ldots,a_n$ are pairwise relatively prime positive integers,

then $M_i = \dfrac{(a_1a_2\cdots a_n)}{a_i} $ is relatively prime to $a_i$ ?

This is supposed to be an obvious step in the proof of Chinese remainder theorem, but to me it is not obvious.

  • 0
    @MathGems: Perhaps my ring theory colleagues misinformed me, then.2012-02-07

3 Answers 3

2

Since $\gcd(a_j,a_i) = 1$ when $i \neq j$, this means that each $a_j$ has no common prime factors with $a_i$. Thus neither does $M_i$.

What is really going on is that if $\gcd(a_j, N) =1$ for $j = 1, \dots, n$, then $\gcd(a_1a_2\dots a_n,N) = 1$ as well.

1

Hint: $\:(a, m) = 1\ \iff\ a$ is a unit (invertible) mod $m$. But units are closed under product since $(xy)^{-1} = y^{-1} x^{-1}$. So all $a_i$ units implies their product is a unit mod $m$, so it is coprime to $m$.

1

I always like to use that $(a,b)=1$ if and only if $ax+by=1$ has integer solutions $x,y$.

We'll prove the lemma for $i=1$.

Then for $j>1$, there are $x_j,y_j$ such that $a_1x_j + a_jy_j = 1$, since the numbers are pairwise relatively prime.

Now multiply these together to get: $1 = \prod_{j>1} (a_1x_j + a_jy_j)$.

But you can expand that product out, and every term has either at least one multiple of $a_1$ in it, or consists of $\prod_{j>1} a_jy_j$. That means we have a solution to:

$a_1X + \left(\prod_{j>1} a_j\right)Y=1$