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)$.

  • $\begingroup$ Where are you stuck? $\endgroup$ – Bill Dubuque Jan 14 '15 at 21:17
  • $\begingroup$ It's not a matter of being stuck is a matter of realizing if this is the same question worded differently $\endgroup$ – Username Unknown Jan 14 '15 at 21:18
  • $\begingroup$ 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$? $\endgroup$ – andrepd Jan 14 '15 at 21:19
  • $\begingroup$ @andrepd Thank you for answering my question. So it is a generalization. I will contunie with the proof then thank you $\endgroup$ – 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$


there is no need for Bezout's, etc.

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)$.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.