prove it!!!

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

Unread post by Mahfuz Sobhan » Tue Nov 17, 2015 5:56 pm

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:110
Joined:Sat Feb 07, 2015 9:47 pm

Re: prove it!!!

Unread post by rah4927 » Wed Nov 18, 2015 12:20 am

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

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

Re: prove it!!!

Unread post by nayel » Sun Nov 22, 2015 7:14 am

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

Post Reply