Theorem 1. Given integers $a$, $b$, and $c$ with $a$ and $b$ not both $0$, there exist $x,y\in\mathbb{Z}$ such that $ax+by=c$ if and only if $(a,b)|c$.

Proof. Left as an exercise.

Corollary 2. Let $a$ and $b$ be integers. Then there exist $x,y\in\mathbb{Z}$ such that $ax+by=1$ if and only if $(a,b)=1$ i.e. $a$ and $b$ are relatively prime.

Corollary 3. Let $a,a’,b\in\mathbb{Z}$. If $(a,b)=1$ and $(a’,b)=1$, then $(aa’,b)=1$.

Proof. Since $(a,b)=1$ and $(a’,b)=1$, there exist $x,y,x’,y’\in\mathbb{Z}$ such that $ax+by=1$ and $a’x’+by’=1$. Now, \begin{align*}1&=(ax+by)(a’x’+by’)\\&=aa’xx’+b(axy’+a’x’y+byy’)\end{align*} Hence, $(aa’,b)=1$.

Theorem 4. If $a,b$ and $c$ are integers such that $(a,b)=1$ and $a|bc$, then $a|c$.

Proof. Since $(a,b)=1$, there exist $x,y\in\mathbb{Z}$ such that $ax+by=1$. So, we obtain $acx+bcy=c$. Since $a|ac$ and $a|bc$, $a|c$.

Remark. $a|bc$ does not necessarily imply that $a|b$ or $a|c$. For example, $6|36=4\cdot 9$ but $6\not|4$ and $6\not|9$. However, the following theorem holds.

Theorem 5. If $p$ is a prime number and $p|ab$, then $p|a$ or $p|b$.

Proof. Let $p$ be a prime number and $p|ab$. Suppose that $p\not|a$ and $p\not|b$. Since $p$ is prime and $p\not|a$, $(p,a)=1$ and so $px+ay=1$ for some $x,y\in\mathbb{Z}$. Now, $p|pbx+aby=b$ but this is a contradiction to the assumption that $p\not|b$. Therefore, $p|a$ or $p|b$.

Theorem 6. If $a$ and $b$ are integers and $(a,b)=d$, then $\frac{a}{d}$ and $\frac{b}{d}$ are relatively prime.

Proof. Since $(a,b)=d$, there exist $x,y\in\mathbb{Z}$ such that $ax+by=d$. Dividing the equation by $d$, we obtain

$\frac{a}{d}x+\frac{b}{d}y=1$. By theorem 1, this implies that $\left(\frac{a}{d},\frac{b}{d}\right)=1$.

Example 1. Consider the equation $9x+24y=15$. Since $(9,24)=3$ and $3|15$, from theorem 1, we know that a solution exist. First, we can find a solution to $9x+24y=3$ using the Euclidean algorithm as seen before. \begin{align*}24&=9\cdot 2+6\\9&=6\cdot 1+3\\6&=3\cdot 2+0\end{align*} Thus, \begin{align*}3&=9-6\cdot 1\\&=9-(24-9\cdot 2)\cdot 1\\&=9\cdot 3+24\cdot(-1)\end{align*} Hence, $x’=3$ and $y’=-1$ is a solution to $9x+24y=3$ and thereby $x=5x’=15$ and $y=5y’=-5$ is a solution to $9x+24y=15$. Finding a solution is not a big deal. But there are other solutions. For instance, $x=-1$ and $y=1$ is also a solution to $9x+24y=15$. How do we find other solutions? We now turn our attention to this question.

Suppose that $(x_0,y_0)$ is a solution to \begin{equation}\label{eq:lineqn}ax+by=c\end{equation} Then \begin{equation}\label{eq:lineqn2}ax_0+by_0=c\end{equation} Subtracting \eqref{eq:lineqn2} from \eqref{eq:lineqn}, we obtain \begin{equation}\label{eq:lineqn3}a(x-x_0)=b(y_0-y)\end{equation} Let $d=(a,b)$. Dividing \eqref{eq:lineqn3} by $d$, we obtain \begin{equation}\label{eq:lineqn4}\frac{a}{d}(x-x_0)=\frac{b}{d}(y_0-y)\end{equation} This means that $\frac{a}{d}|\frac{b}{d}(y_0-y)$. Since $\left(\frac{a}{d},\frac{b}{d}\right)=1$, by theorem 2, $\frac{a}{d}|y_0-y$ and so, $y_0-y=\frac{a}{d}t$ for some $t\in\mathbb{Z}$. From \eqref{eq:lineqn4} we also obtain $x-x_0=\frac{b}{d}t$. Therefore, $x$ and $y$ are written as \begin{equation}\label{eq:lineqnsol}x=x_0+\frac{b}{d}t,\ y=y_0-\frac{a}{d}t\end{equation} where $t\in\mathbb{Z}$. Conversely, any $(x,y)$ in the form \eqref{eq:lineqnsol} satisfies the equation \eqref{eq:lineqn}. $$a\left(x_0+\frac{b}{d}t\right)+b\left(y_0-\frac{a}{d}t\right)=ax_0+by_0=c$$

Theorem 7. Suppose that $a\ne 0$, $b\ne 0$, and $c$ are integers. Let $(x_0,y_0)$ be a particular solution to $ax+by=c$. Then all solutions to $ax+by=c$ are given by $$x=x_0+\frac{b}{d}t,\ y=y_0-\frac{a}{d}t$$ where $t\in\mathbb{Z}$ and $(a,b)=d$.

Example. In example 1, we found $(x_0,y_0)=(15,-5)$. So by theorem 6, all solutions to $9x+24y=15$ are given by $$x=15+8t,\ y=-5-3t$$ where $t\in\mathbb{Z}$.

Example. Find all positive integers $x,y$ such that $4x+6y=100$.

Solution. $(4,6)=2$ and $2|100$, so a solution exists.

$6=4\cdot 1+2$ i.e. $2=4\cdot (-1)+6\cdot 1$. $x_0=-50$ and $y_0=50$ is a particular solution to $4x+6y=100$. By theorem 3, all solutions are given by $$x=-50+3t,\ y=50-2t$$ where $t\in\mathbb{Z}$. Since $x$ and $y$ are required to be positive, we find that $17\leq t\leq 24$. The following table shows all those solutions. $$\begin{array}{|c||c|c|c|c|c|c|c|c|}\hline t & 17 & 18 & 19 & 20 & 21 & 22 & 23 & 24\\\hline x & 1 & 4 & 7 & 10 & 13 & 16 & 19 & 22\\\hline y & 16 & 14 & 12 & 10 & 8 & 6 & 4 & 2\\\hline\end{array}$$

Example. A man paid \$ 11.37 for some 39-cent pens and 69-cent pens. How many of each did he buy?

Solution. The problem is equivalent to solving the equation \begin{equation}\label{eq:pen}39x+69y=1137\end{equation} where $x$ and $y$ are nonnegative integers. $(39,69)=3$ and $3|1137$, so the equation has a solution. Solving the equation \eqref{eq:pen} is equivalent to solving \begin{equation}\label{eq:pen2}13x+23y=379\end{equation} where $x$ and $y$ are nonnegative integers. Since $(13,23)=1$, by the Euclidean algorithm, one can find a solution $x’=-7$ and $y’=4$ to $13x+23y=1$. $x_0=379x’=-2653$ and $y_0=379\cdot y’=1516$ is then a solution to \eqref{eq:pen2}. By theorem 3, all integer solutions to \eqref{eq:pen2} are given by $$x=-2653+23t,\ y=1516-13t,\ t\in\mathbb{Z}$$ From the conditions $x\geq 0, y\geq 0$, we obtain the inequality $115\frac{8}{23}\leq t\leq 116\frac{8}{23}$. There is only one integer $t=116$ that satisfies the inequality. $x=-2653+23\cdot 116=15$ and $y=1516-13\cdot 116=8$. So, the man bought 15 39-cent pens and 8 69-cent pens.

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.

Definition. We say $a$ divides $b$ and write $a|b$ if there exists $d\in\mathbb{Z}$ such that $b=ad$. We say that $a$ is a divisor of $b$ and that $b$ is a multiple of $a$. If $a|b$ is false, we write $a\not|b$.

Definition. We say $d$ is the greatest common divisor (gcd in short) of $a$ and $b$ if $d$ is the largest of all integers dividing both $a$ and $b$. We write $d=(a,b)$.

Example. Let $a=4$ and $b=6$. The divisors of $4$ are $1$, $-1$, $2$, $-2$, $4$, $-4$. The divisors of $6$ are $1$, $-1$, $2$, $-2$, $3$, $-3$, $6$, $-6$. So the common divisors of $4$ and $6$ are $1$, $-1$, $2$, $-2$ and $2=(4,6)$.

Definition. We say $m$ is the least common multiple (lcm in short) of $a$ and $b$ if $m$ is the smallest of all the positive integers that are multiples of both $a$ and $b$. We write $m=[a,b]$.

Example. Let $a=4$ and $b=6$. The positive multiples of $4$ are $4$, $8$, $12$, $16$, $20$, $24$, $28$, $\cdots$ and the positive multiples of $6$ are $6$, $12$, $18$, $24$, $30$, $\cdots$. Common positive multiples of $4$ and $6$ are $12$, $24$, $\cdots$ and $[4,6]=12$.

Theorem. Given integers $a$, $b$, and $c$,

1. if $a|b$ then $a|bc$.
2. if $a|b$ and $b|c$ then $a|c$.
3. if $a|b$ and $a|c$ then $a|bx+cy$ for any $x,y\in\mathbb{Z}$.

Proof.

1. If $a|b$ then there exists $d\in\mathbb{Z}$ such that $b=ad$. Now $bc=(ad)c=a(dc)$ and $dc\in\mathbb{Z}$ and hence $a|bc$.
2. Let $a|b$ and $b|c$. Then there exist $d_1,d_2\in\mathbb{Z}$ such that $b=ad_1$ and $c=bd_2$. Now we have
   $$c=bd_2=(ad_1)d_2=a(d_1d_2)$$
   and $d_1d_2\in\mathbb{Z}$. Hence, $a|c$.
3. Let $a|b$ and $a|c$. Then there exist $d_1,d_2\in\mathbb{Z}$ such that $b=ad_1$ and $c=ad_2$. For any $x,y\in\mathbb{Z}$ \begin{align*} bx+cy&=(ad_1)x+(ad_2)y\\&=a(d_1x+d_2y) \end{align*}
   and $d_1x+d_2y\in\mathbb{Z}$. Hence, $a|bx+cy$.