# Proof of relative primality

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.

• 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$. Commented Feb 7, 2012 at 19:34
• Note: "primal" is actually a technical term in ring theory, distinct from "prime". "Relative primality" can mean something different in general context. Commented Feb 7, 2012 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?) Commented Feb 7, 2012 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. Commented Feb 7, 2012 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. Commented Feb 7, 2012 at 21:13

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.

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

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