5
$\begingroup$

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?

  • 0
    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.2011-03-12

2 Answers 2

4

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

  • 0
    **COMMENT** +1 nice.2012-04-08
1

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.