Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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.

share|improve this question
    
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$. –  André Nicolas Feb 7 '12 at 19:34
2  
Note: "primal" is actually a technical term in ring theory, distinct from "prime". "Relative primality" can mean something different in general context. –  Arturo Magidin Feb 7 '12 at 19:51
    
@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?) –  Math Gems Feb 7 '12 at 20:53
    
@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. –  Arturo Magidin Feb 7 '12 at 21:00
    
@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. –  Math Gems Feb 7 '12 at 21:13
show 3 more comments

3 Answers

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.

share|improve this answer
add comment

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

share|improve this answer
add comment

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

share|improve this answer
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.