# Integer Multiples of Integers Sum to 1

Let $u=p_1^{n_1} \cdots p_t^{n_t}$ for $p_i$ prime and $n_i \in \mathbb{N}$. Let $m_i = \frac{u}{p_i^{n_i}}$. Then there exist $c_i \in \mathbb{Z}$ such that $c_1 m_1 + \cdots + c_tm_t = 1$.

This is given as a property we are allowed to use in one of our homework questions, but we're not sure why we are allowed to use it. We know it's true for $m_i$ that are relatively prime, but these $m_i$ are specifically not. Can you explain why it still holds?

-
Obviously i was thinking of these as not pairwise relatively prime instead of as a whole. Thanks guys! – dandiellie Mar 11 '11 at 20:56
Perhaps you should mention the entire question since it may have some bearing on the best way to answer. – Bill Dubuque Mar 11 '11 at 21:02
Sorry! I'm not allowed to, but maybe i'll update after i turn in the assignment. Honestly, though, the question has very little to do with this. It's an abstract algebra question related to Abelian groups and the p-component. – dandiellie Mar 12 '11 at 0:25

Hint $\, \ \rm\ \{ c_1 m_1 +\:\cdots\:+c_t\ m_t\ :\ c_i \in \mathbb Z\}\$ is closed under subtraction so, by the lemma below, its least positive element $\rm\:d\:$ is a common divisor of all $\rm\:m_i.\:$ $\rm\:d = 1,\:$ by $\rm\ d\:|\:m_{\,i}\$ and $\rm\:m_{\,i}\:$ is coprime to $\rm\:p_i,\$ so $\rm\:d\:$ is a divisor of $\rm\ p_1^{n_{\ 1}}\:\cdots\:p_t^{n_{\ t}}$ coprime to all its prime factors,$\:$ so $\rm\ d = 1.$

Note $\rm\,\ d\ = gcd(m_1,\:\cdots,\,m_t)\:$ since, being an integer linear combination of the $\rm\:m_i\:$ it is divisible by every common divisor $\rm\:c\:$ of all $\rm\ m_i,\,$ $\rm\ c\mid m_i \Rightarrow\ c\mid c_1 m_1\! +\:\cdots\,+c_t m_t =\, d.\,$ So $\rm\:d\:$ is the greatest common divisor, as a common divisor divisible by every common divisor.

Lemma $\:$ If $\;\rm D\subset\mathbb Z \;$ is closed under subtraction and $\rm D$ contains a nonzero element then $\rm\: D \:$ has a positive element and the least positive element of $\rm\: D\:$ divides every element of $\rm\: D.$

Proof $\rm\,\ D$ has a positive element by $\rm \ 0 \ne d\in D\,$ $\Rightarrow$ $\,\rm d-d = 0\in D\,$ $\Rightarrow$ $\,\rm 0-d = -d\in D.\,$ Let $\rm d$ be the least positive element in $\rm D.\,$ By $\,\rm d\mid n \iff d\mid -n, \;$ if $\,\rm c\in D$ isn't divisible by $\rm d$ then we may assume that $\rm c$ is positive, and the least such. But $\,\rm c-d\,$ is a positive element of $\rm D$ not divisible by $\rm d$ and smaller than $\rm c,\,$ contra leastness of $\rm c.\,$ So $\rm d$ divides every element of $\rm D.$

Remark $\$ Alternatively, if you already have available $\rm\:CRT\:$ (Chinese Remainder Theorem), then simply apply it to solve the system $\rm\ x \equiv 1\ \ (mod\ p_i^{n_{\ i}}).\,$ It gives $\rm\ c_i \equiv\ m_{\:i}^{-1}\ (mod\ p_i^{n_{\ i}}).$

-
COMMENT +1 nice. – draks ... Apr 8 '12 at 18:52

What you need to prove is if $gcd(a_{1},...,a_{i})=1$, then there exists $c_{i}$ such that $\sum c_{i}a_{i}=1$. You may do it via induction.

-