Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

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?

share|cite|improve this question
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
up vote 4 down vote accepted

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

share|cite|improve this answer
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.

share|cite|improve this answer

Your Answer


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.