# 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_k\in\Bbb Z$ st. $\sum_{i=1}^k c_in_i=1$

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!

• @DavidKleiman Great! Thank you! – 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$.

• Thank you for your solution. I have a question. It seems $q>0$, but why? Thank you! – Tony Jan 17 '16 at 6:24
• 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. – Thomas Andrews Jan 17 '16 at 12:00