# 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 hence, by the lemma below, its least positive element $\rm\:d\:$ is a common divisor of all the $\rm\:m_i\:.\:$ Necessarily $\rm\:d = 1\:,\:$ since $\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,$\:$ thus $\rm\ d = 1\:$.

NOTE $\$ Furthermore, $\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 of the $\rm\ m_i\:,\$ $\rm\ c\:|\:m_i\ \Rightarrow\ c\:\ |\ c_1\ m +\:\cdots\:+c_t\ m_t\ =\ d\:.\$ So $\rm\:d\:$ is the greatest common divisor, being a common divisor divisible by every common divisor.

LEMMA $\:$ Suppose $\;\rm D\subset\mathbb Z \;$ is closed under subtraction and that $\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 $\$ First $\rm D$ has a positive element since $\rm\: \ 0 \ne d\in D \ \Rightarrow\ d-d = 0\in D\ \Rightarrow\ 0-d = -d\in D\:.\$ Let $\rm d$ be the least positive element in $\rm D$. Since $\rm d|n \iff d\;|-n, \;$ if $\rm c\in D$ is not divisible by $\rm d$ then we may assume that $\rm c$ is positive, and the least such element. 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\:.\$ QED

REMARK $\$ Alternatively, if you already have available the $\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.

-