# 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? – Gone 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)$.