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.

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

2 Answers 2

up vote 3 down vote accepted

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

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