Theorem 1. Suppose that $a,b\in\mathbb{Z}$ with $0<a<b$. Then there exists uniquely $q,r\in\mathbb{Z}$, $0\leq r<a$, such that
$$b=aq+r$$
Theorem 2. If $a$ and $b$ are positive integers, then
$$(a,b)[a,b]=ab$$
Suppose that $0<a<b$. Then by the division algorithm, there exist uniquely $q,r\in\mathbb{Z}$ such that $b=aq+r$ where $0\leq r<a$. If $d=(a,b)$ then $d|r$. This means $d\leq(a,r)$ since $d$ is a common divisor of $a$ and $r$. Since $(a,r)|a$ and $(a,r)|b$, $(a,r)$ is a common divisor of $a$ and $b$. This implies $(a,r)\leq(a,b)=d$. Thus, $d=(a,r)=(a,b)$. More generally, we have the following lemma holds.
Lemma 3. For any integers $a>0$, $b$, $c$ and $k$, if $a=bk+c$ then $(a,b)=(b,c)$.
Example. Let $a=123$ and $b=504$. Then
$$504=123\cdot 4+12$$
By Lemma, we have
$$(123,504)=(12,123)$$
$$123=12\cdot 10+3$$
By Lemma again, we have
$$(12,123)=(3,12)=3$$
Hence, we obtain $(123,504)=3$.
Theorem 4. (The Euclidean Algorithm) Let $a$ and $b$ be integers, $0<a<b$. Apply the division algorithm repeatedly as follows. \begin{align*}b&=aq_1+r_1,\ 0<r_1<a\\a&=r_1q_2+r_2,\ 0<r_2<r_1\\r_1&=r_2q_3+r_3,\ 0<r_3<r_2\\&\vdots\\r_{n-2}&=r_{n-1}q_n+r_n,\ 0<r_n<r_{n-1}\\r_{n-1}&=r_nq_{n+1}\end{align*}Let $r_n$ be the last nonzero remainder. Then $(a,b)=r_n$
Example. Compute $(158,188)$ using the Euclidean algorithm.
\begin{align*}188&=158\cdot 1+30\\158&=30\cdot 5+8\\30&=8\cdot 3+6\\8&=6\cdot 1+2\\6&=2\cdot 3+0 \end{align*} Hence, $(158,188)=2$.
It is possible to use the Euclidean algorithm to write $(a,b)$ in the form $ax+by$. In the above example, \begin{align*}2&=8-6\cdot 1\\&=8-(30-8\cdot 3)\cdot 1\\&=-30+8\cdot 4\\&=-30+(158-30\cdot 5)\cdot 4\\&=158\cdot 4-30\cdot 21\\&=158\cdot 4-(188-158\cdot 1)\cdot 21\\&=158\cdot 25+188\cdot(-21) \end{align*}
In general, the following property holds.
Theorem 5. (Bézout’s Lemma) If $a$ and $b$ are integers such that $(a,b)$ is defined, then there exist $x,y\in\mathbb{Z}$ such that
\begin{equation}
\label{eq:bezout}
(a,b)=ax+by
\end{equation}
\eqref{eq:bezout} is called the Bézout’s identity.
Corollary 6. If $d$ is any common divisor of $a$ and $b$, not both of which are $0$, then $d|(a,b)$.
Definition. We say $k$ is a linear combination of $a$ and $b$ if there exist $x,y\in\mathbb{Z}$ such that $k=ax+by$.
Theorem 7. Given integers $a\ne 0$ and $b\ne 0$, and $m$, if $a|m$ and $b|m$ then $[a,b]|m$.
Proof. Assume that $\frac{m}{[a,b]}$ is not an integer. Then there exist $q,r\in\mathbb{Z}$ such that $m=[a,b]q+r$, $0<r<[a,b]$. The remainder $r$ is then written as $r=m-q[a,b]$. By assumption, $a|m$, and also $a|[a,b]$. So, $a|r$. By the same argument, we also obtain $b|r$. This means that $r$ is a common multiple of $a$ and $b$. But it is a contradiction to the fact that $0<r<[a,b]$. Hence, $r=0$.
Remark. This theorem and the preceding corollary are dual to each other.