Show that if the gcd of a set of non-negative integers $n_1,n_2,...,n_k$ is 1, then there exists $c_1,c_2,...,c_k\in\Bbb Z$ st. $c_1n_1+c_2n_2+...+c_kn_k=1$. Anyone can help give a understandable proof without those advanced number theory stuff? Thank you!

  • $\begingroup$ @DavidKleiman Great! Thank you! $\endgroup$ – Tony Jan 15 '16 at 19:34

Let $S$ be the set of integers that can bet written in that form:

$$S=\{c_1n_1+c_2n_2+\cdots+c_kn_k\mid c_1,\dots,c_k\in\mathbb Z\}$$

Then $S$ is non-empty and has a positive integer in it (why?) Let $d$ be the least positive integer in $S$.

Then assume $d$ does not divide $n_i$ for some $i$. Write $n_i=dq+r$ with $0\leq r< d$, by the division algorithm.

Now show that $r=n_i-dq\in S$. So $0\leq r<d$. Since $d$ does not divide $n_i$, we have $r>0$. So $r$ is a smaller positive integer in $S$, reaching a contradiction.

Therefore, $d\mid n_i$ for all $i$. Since they have no common factor, you are done - $d=1\in S$.

  • $\begingroup$ Thank you for your solution. I have a question. It seems $q>0$, but why? Thank you! $\endgroup$ – Tony Jan 17 '16 at 6:24
  • $\begingroup$ Ugh, there was a big error in my proof - I had written $d=n_iq+r$ and meant $n_i=dq+r$ with $0\leq r<d$. There is no particular reson to expect $q$ to be positive. $\endgroup$ – Thomas Andrews Jan 17 '16 at 12:00

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.