# Prove that any common divisor of $a$ and $b$ must also divide $m_0$.

I have already proven problem 1 but now that I am working on a different problem from a different set of questions. I am find that Problem 2 is asking for the same thing. I am understanding the question write? Is the proof of (1) will be the same for the proof of (2)?

Problem 1: Let $$a$$ and $$b$$ be positive integers. Suppose there are integers $$u$$ and $$v$$ satisfying $$au+bv=1$$. Prove that $$\gcd(a,b)=1$$.

Problem 2: Let $$a$$ and $$b$$ be two positive integers and $$M$$ the set of all integer linear combinations of $$a$$ and $$b$$. Write $$M^+=\{n \in M: n>0\}.$$ Set $$m_0=\min M^+$$.

$$1.$$ Prove that any common divisor of $$a$$ and $$b$$ must also divide $$m_0$$.

$$2.$$ Prove that $$m_0$$ is a common divisor of $$a$$ and $$b$$. $$\textit{Hint: Apply the division algorithm and write a=qm_0+r.}$$

$$3.$$ Prove that $$m_0=\gcd(a,b)$$.

• Where are you stuck? – Bill Dubuque Jan 14 '15 at 21:17
• It's not a matter of being stuck is a matter of realizing if this is the same question worded differently – Username Unknown Jan 14 '15 at 21:18
• Problem 1 is a special case of Problem 2.3 with $m_0=1$. Can you tell us what you did to prove Problem 1? Do you see how you can generalize for any $m_0$? – andrepd Jan 14 '15 at 21:19
• @andrepd Thank you for answering my question. So it is a generalization. I will contunie with the proof then thank you – Username Unknown Jan 14 '15 at 21:21

$m_0\in M^+$ so $\exists u,v\in\mathbb{N},\,m_0=ua+vb$.
Let $d$ a common divisior of $a$ and $b$. So $\exists k_1,k_2\in\mathbb{N},\,a=k_1d$ and $b=k_2d$.
Thus $m_0=(uk_1+vk_2)d$
for arbitrary integers $a,b$:$\space a=gcd(a,b)i$;$\space\space b=gcd(a,b)j$,$\space$where $i$ and $j$ are relatively prime. relatively prime means the only common divisor they have is $1$. so for arbitrary integer $d$ where $d|a$,$\space d|b$ $d$ must divide $gcd(a,b)$.