## prove it!!!

For discussing Olympiad Level Number Theory problems
Mahfuz Sobhan
Posts: 25
Joined: Sat Feb 07, 2015 5:40 pm

### prove it!!!

Let $$a_1, ........., a_n$$ be any non-zero integers whose g.c.d is $$d$$. Then there exist integers
$$x_1, ....., x_n$$ such that $$a_1 x_1 ++.....+a_n x_n = d$$.

rah4927
Posts: 108
Joined: Sat Feb 07, 2015 9:47 pm

### Re: prove it!!!

An approach is to prove the case $n=2$ and then induct.

nayel
Posts: 268
Joined: Tue Dec 07, 2010 7:38 pm
Location: Dhaka, Bangladesh or Cambridge, UK

### Re: prove it!!!

Let $S=\{a_1x_1+\cdots+a_nx_n:x_1,\dots,x_n\in\mathbb Z\}$. Let $d'$ be the smallest positive element of $S$. Prove the following:

(i) $d$ divides $d'$.

(ii) $d'$ divides $d$.

So $d=d'\in S$ and your conclusion will follow.
"Everything should be made as simple as possible, but not simpler." - Albert Einstein