I am learning Discrete Mathematics myself by reading book titled "Discrete Mathematical Structures" by Kolman, Busby and Ross.
In this book, on Chapter 1, the following theorem is mentioned.
if $d$ is $\gcd(a,b)$, then
(i) $d=sa+tb$ for some integers $s$ and $t$. (These are not necessarily positive)
(ii) if $c$ is any other common divisor of $a$ and $b$, then $c \mid d$
The proof is given as follows.
Let $x$ be the smallest positive that can be written as $sa+tb$ for some integers $s$ and $t$, and let $c$ be a common divisor of $a$ and $b$. Since $c\mid a$ and $c\mid b$, it follows from the Theorem 2 that $c\mid x$, so $c \leq x$. if we can show that $x$ is a common divisor of $a$ and $b$, it will then be the greatest common divisor of $a$ and $b$ and both parts of the theorem will have been proved. By Theorem 1, $a=qx+r$ with $0 \leq r \le x$. Solving for $r,$ we have
$$r=a-qx=a-q(sa+tb)=a-qsa-qtb=(1-qs)a+(-qt)b.$$
If $r$ is not zero, then since $r \leq x$ and $r$ is the sum of a multiple of $a$ and a multiple of $b$, we will have a contradiction to the fact that $x$ is the smallest positive number that is a sum of multiples $a$ and $b$. Thus $r$ must be $0$ and $x\mid a$. In the same way we can show that $x\mid b$, and this completes the proof.
I only understand up to "follows from the Theorem 2 that $c\mid x$, so $c \leq x$." in the theorem. then I understand how $r$ is calculated using Theorem 1. Other than that I can't understand this proof.
How it will prove both the part of the theorem if we show $x$ is a common divisor of $a$ and $b$, it will then be the greatest common divisor of $a$ and $b$ ?
Can somebody please explain this elaborately?
Edit:
Theorem 1: if $n$ and $m$ are integers and $n \gt 0$, we can write $m = qn + r$ for integers $q$ and $r$ with $0 \leq r \lt n$.
Theorem 2: If $a\mid b$ and $a\mid c$, then $a\mid(mb+nc)$, for any integers $m$ and $n$.
Best Answer
The global strategy of the proof is this: if $x$ is the smallest positive that can be written as $sa+tb$ for some integers $s$ and $t$, then $x=\gcd(a,b)$; in particular, $\gcd(a,b)$ can be written as a linear combination of $a$ and $b$ with integer coefficients. And it follows from the fact that $x$ can be written as $sa+tb$ for some integers $s$ and $t$ that if $c\mid a$ and $c\mid b$, then $c\mid x(=sa+tb)$.
In order to prove that $x=\gcd(a,b)$, the authors first prove that every common divisor of $a$ and $b$ is smaller than or equal to $x$. So, if it turns out that $x$ itself is also a common divisor of $a$ and $b$, it will follow that it is the greatest common divisor.
In order to prove that $x\mid a$, the authors note that, if $a=qx+r$ with $0\leqslant r<x$, then$$r=(1−qs)a+(−qt)b.$$So, if $r>0$, $r$ would be a positive number that could be written as a linear combination of $a$ and $b$ with integer coefficients. But $r<x$ and $x$ is the smallest such positive number. So, $r=0$; in other words, $a=qx$ and, in particular, $x\mid a$. By the same argument, $x\mid b$.