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.

$\endgroup$
8
  • $\begingroup$ Note that $M_i$ is the product of all the $a_j$ except for $a_i$. Now use the fact that the product of numbers relatively prime to $a$ is relatively prime to $a$. $\endgroup$
    – André Nicolas
    Commented Feb 7, 2012 at 19:34
  • 2
    $\begingroup$ Note: "primal" is actually a technical term in ring theory, distinct from "prime". "Relative primality" can mean something different in general context. $\endgroup$
    – Arturo Magidin
    Commented Feb 7, 2012 at 19:51
  • $\begingroup$ @Arturo If you refer to Cohn's notion of primal, then I don't think there is any danger of confusion, since "relatively primal" is not in use (what could it mean?) $\endgroup$
    – Math Gems
    Commented Feb 7, 2012 at 20:53
  • $\begingroup$ @MathGems: In a commutative ring, an ideal $Q$ is primal if all elements that are not relatively prime to $Q$ form an ideal. An element $a$ is relatively prime to $Q$ if $ab\in Q$ implies $b\in Q$. Since two elements are "relatively prime" if there is no prime ideal that contains both, they would be "relatively primal" if there is no primal ideal that contains both. $\endgroup$
    – Arturo Magidin
    Commented Feb 7, 2012 at 21:00
  • $\begingroup$ @Arturo That meaning of "relatively primal" does not appear to be in use, so, again, there does not appear to be any danger of confusion. $\endgroup$
    – Math Gems
    Commented Feb 7, 2012 at 21:13

3 Answers 3

Reset to default
2
$\begingroup$

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.

$\endgroup$
1
$\begingroup$

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

$\endgroup$
1
$\begingroup$

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

$\endgroup$

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .