\documentclass[numbers=enddot,12pt,final,onecolumn,notitlepage]{scrartcl}%
\usepackage[headsepline,footsepline,manualmark]{scrlayer-scrpage}
\usepackage[all,cmtip]{xy}
\usepackage{amssymb}
\usepackage{amsmath}
\usepackage{amsthm}
\usepackage{framed}
\usepackage{comment}
\usepackage{color}
\usepackage[breaklinks=True]{hyperref}
\usepackage[sc]{mathpazo}
\usepackage[T1]{fontenc}
\usepackage{needspace}
\usepackage{tabls}
\usepackage{tikz}
\usepackage{bbding}
%TCIDATA{OutputFilter=latex2.dll}
%TCIDATA{Version=5.50.0.2960}
%TCIDATA{LastRevised=Thursday, June 08, 2023 13:24:57}
%TCIDATA{SuppressPackageManagement}
%TCIDATA{<META NAME="GraphicsSave" CONTENT="32">}
%TCIDATA{<META NAME="SaveForMode" CONTENT="1">}
%TCIDATA{BibliographyScheme=Manual}
%TCIDATA{Language=American English}
%BeginMSIPreambleData
\providecommand{\U}[1]{\protect\rule{.1in}{.1in}}
%EndMSIPreambleData
\usetikzlibrary{arrows.meta}
\usetikzlibrary{chains}
\usetikzlibrary{shapes}
\usetikzlibrary{decorations.pathmorphing}
\newcounter{exer}
\newcounter{exera}
\theoremstyle{definition}
\newtheorem{theo}{Theorem}[subsection]
\newenvironment{theorem}[1][]
{\begin{theo}[#1]\begin{leftbar}}
{\end{leftbar}\end{theo}}
\newtheorem{lem}[theo]{Lemma}
\newenvironment{lemma}[1][]
{\begin{lem}[#1]\begin{leftbar}}
{\end{leftbar}\end{lem}}
\newtheorem{prop}[theo]{Proposition}
\newenvironment{proposition}[1][]
{\begin{prop}[#1]\begin{leftbar}}
{\end{leftbar}\end{prop}}
\newtheorem{defi}[theo]{Definition}
\newenvironment{definition}[1][]
{\begin{defi}[#1]\begin{leftbar}}
{\end{leftbar}\end{defi}}
\newtheorem{remk}[theo]{Remark}
\newenvironment{remark}[1][]
{\begin{remk}[#1]\begin{leftbar}}
{\end{leftbar}\end{remk}}
\newtheorem{coro}[theo]{Corollary}
\newenvironment{corollary}[1][]
{\begin{coro}[#1]\begin{leftbar}}
{\end{leftbar}\end{coro}}
\newtheorem{conv}[theo]{Convention}
\newenvironment{convention}[1][]
{\begin{conv}[#1]\begin{leftbar}}
{\end{leftbar}\end{conv}}
\newtheorem{quest}[theo]{Question}
\newenvironment{question}[1][]
{\begin{quest}[#1]\begin{leftbar}}
{\end{leftbar}\end{quest}}
\newtheorem{warn}[theo]{Warning}
\newenvironment{warning}[1][]
{\begin{warn}[#1]\begin{leftbar}}
{\end{leftbar}\end{warn}}
\newtheorem{conj}[theo]{Conjecture}
\newenvironment{conjecture}[1][]
{\begin{conj}[#1]\begin{leftbar}}
{\end{leftbar}\end{conj}}
\newtheorem{exam}[theo]{Example}
\newenvironment{example}[1][]
{\begin{exam}[#1]\begin{leftbar}}
{\end{leftbar}\end{exam}}
\newtheorem{exmp}[exer]{Exercise}
\newenvironment{exercise}[1][]
{\begin{exmp}[#1]\begin{leftbar}}
{\end{leftbar}\end{exmp}}
\newenvironment{statement}{\begin{quote}}{\end{quote}}
\newenvironment{fineprint}{\begin{small}}{\end{small}}
\iffalse
\newenvironment{proof}[1][Proof]{\noindent\textbf{#1.} }{\ \rule{0.5em}{0.5em}}
\newenvironment{convention}[1][Convention]{\noindent\textbf{#1.} }{\ \rule{0.5em}{0.5em}}
\newenvironment{question}[1][Question]{\noindent\textbf{#1.} }{\ \rule{0.5em}{0.5em}}
\fi
\let\sumnonlimits\sum
\let\prodnonlimits\prod
\let\cupnonlimits\bigcup
\let\capnonlimits\bigcap
\renewcommand{\sum}{\sumnonlimits\limits}
\renewcommand{\prod}{\prodnonlimits\limits}
\renewcommand{\bigcup}{\cupnonlimits\limits}
\renewcommand{\bigcap}{\capnonlimits\limits}
\newcommand\arxiv[1]{\href{http://www.arxiv.org/abs/#1}{\texttt{arXiv:#1}}}
\setlength\tablinesep{3pt}
\setlength\arraylinesep{3pt}
\setlength\extrarulesep{3pt}
\setlength\textheight{22.5cm}
\setlength\textwidth{14.8cm}
\newenvironment{verlong}{}{}
\newenvironment{vershort}{}{}
\newenvironment{noncompile}{}{}
\excludecomment{verlong}
\includecomment{vershort}
\excludecomment{noncompile}
\newcommand{\defn}[1]{{\color{darkred}\emph{#1}}}
\newcommand{\CC}{\mathbb{C}}
\newcommand{\RR}{\mathbb{R}}
\newcommand{\QQ}{\mathbb{Q}}
\newcommand{\NN}{\mathbb{N}}
\newcommand{\ZZ}{\mathbb{Z}}
\newcommand{\KK}{\mathbb{K}}
\newcommand{\set}[1]{\left\{ #1 \right\}}
\newcommand{\abs}[1]{\left| #1 \right|}
\newcommand{\tup}[1]{\left( #1 \right)}
\newcommand{\ive}[1]{\left[ #1 \right]}
\newcommand{\floor}[1]{\left\lfloor #1 \right\rfloor}
\newcommand{\are}{\ar@{-}}
\newcommand{\arebi}[1][]{\ar@{<-}@/_/[#1] \ar@/^/[#1]}
\newcommand{\of}{\text{ of }}
\newtheoremstyle{plainsl}
{8pt plus 2pt minus 4pt}
{8pt plus 2pt minus 4pt}
{\slshape}
{0pt}
{\bfseries}
{.}
{5pt plus 1pt minus 1pt}
{}
\theoremstyle{plainsl}
\ihead{Greatest common divisors, version \today}
\ohead{page \thepage}
\cfoot{}
\begin{document}
\section*{Greatest common divisors: an introduction}

\subsection{Division with remainder (recall)}

If $a$ and $b$ are two integers with $b>0$, then there is a unique pair
$\left(  q,r\right)  $ with%
\[
q\in\mathbb{Z}\ \ \ \ \ \ \ \ \ \ \text{and}\ \ \ \ \ \ \ \ \ \ r\in\left\{
0,1,\ldots,b-1\right\}  \ \ \ \ \ \ \ \ \ \ \text{and}%
\ \ \ \ \ \ \ \ \ \ a=qb+r.
\]
This pair $\left(  q,r\right)  $ is called the \textbf{quo-rem pair} of $a$
and $b$. Specifically, $q$ is called the \textbf{quotient} and $r$ the
\textbf{remainder} of the division of $a$ by $b$. We use the notations%
\[
a//b:=q\ \ \ \ \ \ \ \ \ \ \text{and}\ \ \ \ \ \ \ \ \ \ a\%b:=r.
\]


For example,
\begin{align*}
7//3  &  =2\ \ \ \ \ \ \ \ \ \ \text{and}\ \ \ \ \ \ \ \ \ \ 7\%3=1;\\
6//3  &  =2\ \ \ \ \ \ \ \ \ \ \text{and}\ \ \ \ \ \ \ \ \ \ 6\%3=0;\\
\left(  -1\right)  //3  &  =-1\ \ \ \ \ \ \ \ \ \ \text{and}%
\ \ \ \ \ \ \ \ \ \ \left(  -1\right)  \%3=2.
\end{align*}


\subsection{Greatest common divisors}

\subsubsection{Definition}

\begin{definition}
Let $a$ and $b$ be two integers.

\textbf{(a)} The \textbf{common divisors} of $a$ and $b$ are the integers that
divide both $a$ and $b$ simultaneously.

\textbf{(b)} The \textbf{greatest common divisor} of $a$ and $b$ is the
largest of all common divisors of $a$ and $b$, provided that $a$ and $b$ are
not both $0$. If $a$ and $b$ are both $0$, it is defined to be $0$ instead.

We denote the greatest common divisor of $a$ and $b$ by $\gcd\left(
a,b\right)  $, and we refer to it as the \textbf{gcd} of $a$ and $b$.
\end{definition}

Some examples:

\begin{itemize}
\item What is $\gcd\left(  4,6\right)  $ ?

The divisors of $4$ are $-4,-2,-1,1,2,4$.

The divisors of $6$ are $-6,-3,-2,-1,1,2,3,6$.

Thus, the common divisors of $4$ and $6$ are $-2,-1,1,2$.

So the greatest common divisor of $4$ and $6$ is $2$. That is, $\gcd\left(
4,6\right)  =2$.

\item What is $\gcd\left(  0,5\right)  $ ?

The divisors of $0$ are all integers (since $0=x\cdot0$ for each integer $x$).

The divisors of $5$ are $-5,-1,1,5$.

So the common divisors of $0$ and $5$ are $-5,-1,1,5$.

Thus, $\gcd\left(  0,5\right)  =5$.

\item By definition, $\gcd\left(  0,0\right)  =0$. It is not literally the
largest of all common divisors of $0$ and $0$, because there is no largest
integer. (This is why we had to make an exception for the case
\textquotedblleft$a$ and $b$ are both $0$\textquotedblright\ when defining the gcd!)
\end{itemize}

Let us check that $\gcd\left(  a,b\right)  $ is well-defined -- i.e., that if
$a$ and $b$ are two integers that are not both $0$, then there \textbf{is} a
largest among all common divisors of $a$ and $b$. In fact:

\begin{itemize}
\item The number $1$ is always a common divisor of $a$ and $b$, so there is
\textbf{at least one} common divisor of $a$ and $b$.

\item At least one of the numbers $a$ and $b$ is nonzero and thus has only
finitely many divisors, so there are \textbf{only finitely many} common
divisors of $a$ and $b$.
\end{itemize}

Hence, the set of all common divisors of $a$ and $b$ is nonempty and finite,
and thus has a largest element. This shows that $\gcd\left(  a,b\right)  $ is well-defined.

\bigskip

The above definition gives a stupid but functional algorithm to compute
$\gcd\left(  a,b\right)  $: Just run over all divisors of $a$ and check which
of them divide $b$ (at least if $a\neq0$). This is slow when $a$ is a large number.

However, is there a better way?

\subsubsection{Basic properties}

There is one, and in order to find it, we shall first show a sequence of basic
properties of gcds. First, some very simple results:

\begin{proposition}
\label{prop.ent.gcd.nonneg}Let $a,b\in\mathbb{Z}$. Then, $\gcd\left(
a,b\right)  $ is a nonnegative integer.
\end{proposition}

\begin{proof}
If $a$ and $b$ are both $0$, this gcd is $0$. Else, it is $\geq1$ (since $1$
is a common divisor).
\end{proof}

\begin{proposition}
\label{prop.ent.gcd.comm}We have $\gcd\left(  a,b\right)  =\gcd\left(
b,a\right)  $ for all $a,b\in\mathbb{Z}$.
\end{proposition}

\begin{proof}
Obvious ($a$ and $b$ play equal roles in the definition).
\end{proof}

\begin{proposition}
\label{prop.ent.gcd.div}We have $\gcd\left(  a,b\right)  \mid a$ and
$\gcd\left(  a,b\right)  \mid b$.
\end{proposition}

\begin{proof}
Obvious for $a=b=0$. Also obvious otherwise.
\end{proof}

\begin{proposition}
\label{prop.ent.gcd.-a}Let $a,b\in\mathbb{Z}$. Then, $\gcd\left(  -a,b\right)
=\gcd\left(  a,b\right)  $ and $\gcd\left(  a,-b\right)  =\gcd\left(
a,b\right)  $.
\end{proposition}

\begin{proof}
For any integer $c$, the number $-c$ has the same divisors as $c$. Thus, the
common divisors of $-a$ and $b$ are exactly those of $a$ and $b$. Hence, in
particular, $\gcd\left(  -a,b\right)  =\gcd\left(  a,b\right)  $. Similarly,
we can show $\gcd\left(  a,-b\right)  =\gcd\left(  a,b\right)  $.
\end{proof}

\begin{proposition}
\label{prop.ent.gcd.0}Let $a\in\mathbb{Z}$. Then, $\gcd\left(  a,0\right)
=\gcd\left(  0,a\right)  =\left\vert a\right\vert $.
\end{proposition}

\begin{proof}
Every integer divides $0$. Thus, the common divisors of $a$ and $0$ are
precisely the divisors of $a$. If $a$ is nonzero, then the greatest among
those is $\left\vert a\right\vert $, so that Proposition \ref{prop.ent.gcd.0}
holds. If $a=0$, then $\gcd\left(  0,0\right)  =0$ gets us to the same conclusion.
\end{proof}

\subsubsection{The Euclidean recursion}

Next we shall show something subtler:

\begin{proposition}
\label{prop.ent.gcd.ua+b}Let $a,b,u\in\mathbb{Z}$. Then,%
\[
\gcd\left(  a,\ ua+b\right)  =\gcd\left(  a,b\right)  .
\]
In other words, the gcd of two integers does not change if you add a multiple
of one to the other.
\end{proposition}

\begin{proof}
This is trivial if $a=0$ (because $ua+b=b$ in this case), so let us assume
that $a\neq0$. Thus, both gcds are taken in the literal sense (i.e., they are
literally greatest among the common divisors of the respective numbers).

We shall show that the common divisors of $a$ and $ua+b$ are precisely the
common divisors of $a$ and $b$. To prove this, we must prove the following two claims:

\begin{statement}
\textit{Claim 1:} Every common divisor of $a$ and $ua+b$ is a common divisor
of $a$ and $b$.
\end{statement}

\begin{statement}
\textit{Claim 2:} Every common divisor of $a$ and $b$ is a common divisor of
$a$ and $ua+b$.
\end{statement}

\begin{proof}
[Proof of Claim 2.]Let $d$ be a common divisor of $a$ and $b$. We must prove
that $d$ is a common divisor of $a$ and $ua+b$. In other words, we must prove
that $d\mid a$ and $d\mid ua+b$.

Of course, $d\mid a$ is clear by definition of $d$. Moreover, from $d\mid
a\mid ua$ and $d\mid b$, we see that the two numbers $ua$ and $b$ are
multiples of $d$. Hence, their sum $ua+b$ is a multiple of $d$ as well (since
a sum of two multiples of $d$ is again a multiple of $d$). In other words,
$d\mid ua+b$. Thus, $d\mid a$ and $d\mid ua+b$ are both proved. In other
words, Claim 2 is proved.
\end{proof}

\begin{proof}
[Proof of Claim 1.]Let $c=ua+b$. Then, $\left(  -u\right)
a+c=\underbrace{\left(  -u\right)  a+ua}_{=0}+b=b$. However, Claim 1 (applied
to $-u$ and $c$ instead of $u$ and $b$) yields that every common divisor of
$a$ and $\left(  -u\right)  a+c$ is a common divisor of $a$ and $c$. In other
words, every common divisor of $a$ and $b$ is a common divisor of $a$ and
$ua+b$ (since $\left(  -u\right)  a+c=b$ and $c=ua+b$). This proves Claim 1.
\end{proof}

Having proved both claims, we conclude that the common divisors of $a$ and
$ua+b$ are precisely the common divisors of $a$ and $b$. Thus, the greatest
common divisor of $a$ and $ua+b$ is the greatest common divisor of $a$ and
$b$. This proves Proposition \ref{prop.ent.gcd.ua+b}.
\end{proof}

\begin{corollary}
[Euclidean recursion for the gcd]\label{cor.ent.gcd.euclrec}Let $a\in
\mathbb{Z}$, and let $b$ be a positive integer. Then,%
\[
\gcd\left(  a,b\right)  =\gcd\left(  b,\ a\%b\right)  .
\]

\end{corollary}

\begin{proof}
Let $q$ and $r$ be the quotient and the remainder of the division of $a$ by
$b$. Then, $a=qb+r$ (by the definition of quotient and remainder) and $a\%b=r$
(by the definition of $a\%b$).

Now, Proposition \ref{prop.ent.gcd.comm} yields%
\begin{align*}
\gcd\left(  a,b\right)   &  =\gcd\left(  b,a\right)  =\gcd\left(
b,\ qb+r\right)  \ \ \ \ \ \ \ \ \ \ \left(  \text{since }a=qb+r\right) \\
&  =\gcd\left(  b,r\right)  \ \ \ \ \ \ \ \ \ \ \left(
\begin{array}
[c]{c}%
\text{by Proposition \ref{prop.ent.gcd.ua+b},}\\
\text{applied to }b,r,q\text{ instead of }a,b,c
\end{array}
\right) \\
&  =\gcd\left(  b,\ a\%b\right)  \ \ \ \ \ \ \ \ \ \ \left(  \text{since
}r=a\%b\right)  .
\end{align*}
This proves Corollary \ref{cor.ent.gcd.euclrec}.
\end{proof}

\subsubsection{The Euclidean algorithm}

Let us put this corollary to some use: We shall compute some gcds by
repeatedly simplifying them using Corollary \ref{cor.ent.gcd.euclrec}. For
instance,
\begin{align*}
\gcd\left(  179,\ 18\right)   &  =\gcd\left(  18,\ 179\%18\right)
\ \ \ \ \ \ \ \ \ \ \left(  \text{by Corollary \ref{cor.ent.gcd.euclrec}%
}\right) \\
&  =\gcd\left(  18,\ 17\right)  \ \ \ \ \ \ \ \ \ \ \left(  \text{since
}179\%18=17\right) \\
&  =\gcd\left(  17,\ 18\%17\right)  \ \ \ \ \ \ \ \ \ \ \left(  \text{by
Corollary \ref{cor.ent.gcd.euclrec}}\right) \\
&  =\gcd\left(  17,\ 1\right)  \ \ \ \ \ \ \ \ \ \ \left(  \text{since
}18\%17=1\right) \\
&  =\gcd\left(  1,\ 17\%1\right)  \ \ \ \ \ \ \ \ \ \ \left(  \text{by
Corollary \ref{cor.ent.gcd.euclrec}}\right) \\
&  =\gcd\left(  1,\ 0\right)  \ \ \ \ \ \ \ \ \ \ \left(  \text{since
}17\%1=0\right) \\
&  =\left\vert 1\right\vert \ \ \ \ \ \ \ \ \ \ \left(  \text{by Proposition
\ref{prop.ent.gcd.0}}\right) \\
&  =1
\end{align*}
and%
\begin{align*}
\gcd\left(  73,\ 333\right)   &  =\gcd\left(  333,\ 73\%333\right)
\ \ \ \ \ \ \ \ \ \ \left(  \text{by Corollary \ref{cor.ent.gcd.euclrec}%
}\right) \\
&  =\gcd\left(  333,\ 73\right) \\
&  =\gcd\left(  73,\ 333\%73\right)  \ \ \ \ \ \ \ \ \ \ \left(  \text{by
Corollary \ref{cor.ent.gcd.euclrec}}\right) \\
&  =\gcd\left(  73,\ 41\right) \\
&  =\gcd\left(  41,\ 73\%41\right)  \ \ \ \ \ \ \ \ \ \ \left(  \text{by
Corollary \ref{cor.ent.gcd.euclrec}}\right) \\
&  =\gcd\left(  41,\ 32\right) \\
&  =\gcd\left(  32,\ 41\%32\right)  \ \ \ \ \ \ \ \ \ \ \left(  \text{by
Corollary \ref{cor.ent.gcd.euclrec}}\right) \\
&  =\gcd\left(  32,\ 9\right) \\
&  =\gcd\left(  9,\ 32\%9\right)  \ \ \ \ \ \ \ \ \ \ \left(  \text{by
Corollary \ref{cor.ent.gcd.euclrec}}\right) \\
&  =\gcd\left(  9,\ 5\right) \\
&  =\gcd\left(  5,\ 9\%5\right)  \ \ \ \ \ \ \ \ \ \ \left(  \text{by
Corollary \ref{cor.ent.gcd.euclrec}}\right) \\
&  =\gcd\left(  5,\ 4\right) \\
&  =\gcd\left(  4,\ 5\%4\right)  \ \ \ \ \ \ \ \ \ \ \left(  \text{by
Corollary \ref{cor.ent.gcd.euclrec}}\right) \\
&  =\gcd\left(  4,\ 1\right) \\
&  =\gcd\left(  1,\ 4\%1\right)  \ \ \ \ \ \ \ \ \ \ \left(  \text{by
Corollary \ref{cor.ent.gcd.euclrec}}\right) \\
&  =\gcd\left(  1,\ 0\right)  =\left\vert 1\right\vert =0.
\end{align*}


These two computations are instances of a general algorithm for computing
$\gcd\left(  a,b\right)  $ for any two integers $a$ and $b$, where $b\geq0$.
This algorithm proceeds as follows:

\begin{itemize}
\item If $b=0$, then the gcd is $\left\vert a\right\vert $.

\item If $b>0$, then we replace $a$ and $b$ by $b$ and $a\%b$ and recurse
(i.e., we apply the same algorithm again to $b$ and $a\%b$ instead of $a$ and
$b$).
\end{itemize}

In Python, this algorithm can be implemented as follows:
\begin{verbatim}
  def gcd(a, b): # for b nonnegative
    if b == 0:
      return abs(a) # this is |a|
    return gcd(b, a%b)
\end{verbatim}

This algorithm is called the \textbf{Euclidean algorithm}. It will terminate
because at each step, $b$ (the second argument) gets smaller:%
\[
a\%b<b\ \ \ \ \ \ \ \ \ \ \left(  \text{since }a\%b\in\left\{  0,1,\ldots
,b-1\right\}  \text{ by the definition of remainders}\right)  .
\]


Moreover, it will terminate fairly quickly, because of the following fact:

\begin{proposition}
Assume that $a$ and $b$ are positive integers. Then, at every step of the
Euclidean algorithm except perhaps for the first step, the product $ab$ drops
by at least a factor of $2$.
\end{proposition}

\begin{proof}
[Proof sketch.]A step replaces a pair $\left(  a,b\right)  $ by $\left(
b,\ a\%b\right)  $. Note that $b>a\%b$ (since $a\%b\in\left\{  0,1,\ldots
,b-1\right\}  $ by the definition of remainders), so that we always have $a>b$
after the first step.

Now, if $a>b$, then the quotient $q$ and the remainder $r=a\%b$ of the
division of $a$ by $b$ satisfy $a=\underbrace{q}_{\substack{\geq
1\\\text{(since }a>b\text{)}}}b+r\geq\underbrace{b}_{>r}+r>r+r=2r$, so that
$r<\dfrac{a}{2}$. In other words, $a\%b<\dfrac{a}{2}$. Thus, the step that
replaces $a$ and $b$ by $b$ and $b\%a$ turns the product $ab$ into
$b\underbrace{\left(  a\%b\right)  }_{<\dfrac{a}{2}}<b\cdot\dfrac{a}{2}%
=\dfrac{ab}{2}$. Hence, the product drops by at least a factor of $2$ when we
perform this step.
\end{proof}

Hence, the Euclidean algorithm (when applied to two positive integers $a$ and
$b$) terminates after at most $2+\log_{2}\left(  ab\right)  $ many steps. For
instance, if $a$ and $b$ are $20$-digit integers, then $2+\log_{2}\left(
ab\right)  <2+\log_{2}\left(  10^{20}\cdot10^{20}\right)  \approx135$, which
is a very manageable number of steps.

Thus, the Euclidean algorithm makes gcds easy to compute. (And because of
$\gcd\left(  a,b\right)  =\gcd\left(  a,-b\right)  $, we can easily extend it
to the case when $b$ is negative, so that it will work for any integers $a$
and $b$.)

\subsubsection{Bezout's theorem, and the extended Euclidean algorithm}

We can tweak the Euclidean algorithm to produce more than just the gcd. But
what else could we want?

Assume that your country has only two kinds of coins: $3$-cent coins and
$5$-cent coins. You want to pay exactly $1$ cent. You can get change (but only
in $3$-cent and $5$-cent coins). Can you do it, and how?

Yes, you can do this by paying two $5$-cent coins and getting three $3$-cent
coins in return. The reason why this works is that%
\[
2\cdot5+\left(  -3\right)  \cdot3=1.
\]


Similarly, can you pay $1$ cent with $5$-cent coins and $7$-cent coins (with
change)? Yes:%
\[
3\cdot7+\left(  -4\right)  \cdot5=1.
\]


Can you pay $1$ cent with $4$-cent coins and $6$-cent coins (with change)? No.
In fact, any amount you can pay has the form $x\cdot4+y\cdot6$ for
$x,y\in\mathbb{Z}$, and thus is even. But $1$ is not even.

In general, the only amounts you could possibly pay with $a$-cent coins and
$b$-cent coins are multiples of $\gcd\left(  a,b\right)  $. But is this the
only requirement? Can you pay exactly $\gcd\left(  a,b\right)  $ cents?

Bezout's theorem says \textquotedblleft yes\textquotedblright\ (if you can get change):

\begin{theorem}
[Bezout's theorem]\label{thm.ent.gcd.bezout}Let $a$ and $b$ be two integers.
Then, there exist two integers $x$ and $y$ such that%
\[
\gcd\left(  a,b\right)  =xa+yb.
\]

\end{theorem}

This theorem is not just amusing but actually very useful. We will sketch a
proof by strong induction. The idea of the proof is: You're interested in
representing the gcd of two numbers $a$ and $b$ as a multiple of $a$ plus a
multiple of $b$. Such a representation will be called a \textbf{Bezout pair}
for $\left(  a,b\right)  $. We provide an algorithm for finding such a Bezout
pair by piggybacking on the Euclidean algorithm for computing $\gcd\left(
a,b\right)  $.

Let's make this more precise:

\begin{definition}
Let $a$ and $b$ be two integers. A \textbf{Bezout pair} for $\left(
a,b\right)  $ will mean a pair $\left(  x,y\right)  $ of integers such that%
\[
\gcd\left(  a,b\right)  =xa+yb.
\]

\end{definition}

So we must prove that every pair $\left(  a,b\right)  $ of integers has a
Bezout pair. We observe the following:

\begin{lemma}
\label{lem.ent.gcd.bezout0}For any integer $a$, there is a Bezout pair for
$\left(  a,0\right)  $, namely $%
\begin{cases}
\left(  1,0\right)  , & \text{if }a\geq0;\\
\left(  -1,0\right)  , & \text{if }a<0.
\end{cases}
$
\end{lemma}

\begin{proof}
Direct verification, since $\gcd\left(  a,0\right)  =\left\vert a\right\vert $.
\end{proof}

\begin{lemma}
\label{lem.ent.gcd.bezout-b}Let $a$ and $b$ be two integers. Let $\left(
u,v\right)  $ be a Bezout pair for $\left(  a,-b\right)  $. Then, $\left(
u,-v\right)  $ is a Bezout pair for $\left(  a,b\right)  $.
\end{lemma}

\begin{proof}
Proposition \ref{prop.ent.gcd.-a} yields%
\begin{align*}
\gcd\left(  a,b\right)   &  =\gcd\left(  a,-b\right) \\
&  =ua+v\left(  -b\right)  \ \ \ \ \ \ \ \ \ \ \left(  \text{since }\left(
u,v\right)  \text{ is a Bezout pair for }\left(  a,-b\right)  \right) \\
&  =ua+\left(  -v\right)  b.
\end{align*}
But this shows precisely that $\left(  u,-v\right)  $ is a Bezout pair for
$\left(  a,b\right)  $.
\end{proof}

\begin{lemma}
[Euclidean recursion for Bezout pairs]\label{lem.ent.gcd.bezout-rem}Let $a$
and $b$ be two integers, where $b>0$. Let $\left(  u,v\right)  $ be a Bezout
pair for $\left(  b,\ a\%b\right)  $. Then, $\left(  v,\ u-v\left(
a//b\right)  \right)  $ is a Bezout pair for $\left(  a,b\right)  $.
\end{lemma}

\begin{proof}
Since $\left(  u,v\right)  $ is a Bezout pair for $\left(  b,\ a\%b\right)  $,
we have
\[
\gcd\left(  b,\ a\%b\right)  =ub+v\left(  a\%b\right)  .
\]
Also, the definition of quotient and remainder yields $a=qb+r$, where $q=a//b$
and $r=a\%b$. In other words,%
\[
a=\left(  a//b\right)  b+\left(  a\%b\right)  .
\]
Hence,
\[
a\%b=a-\left(  a//b\right)  b.
\]


Now, Corollary \ref{cor.ent.gcd.euclrec} yields%
\begin{align*}
\gcd\left(  a,b\right)   &  =\gcd\left(  b,\ a\%b\right)
=ub+v\underbrace{\left(  a\%b\right)  }_{=a-\left(  a//b\right)  b}\\
&  =ub+v\left(  a-\left(  a//b\right)  b\right) \\
&  =ub+va-v\left(  a//b\right)  b\\
&  =\left(  u-v\left(  a//b\right)  \right)  b+va\\
&  =va+\left(  u-v\left(  a//b\right)  \right)  b.
\end{align*}
This shows that $\left(  v,\ u-v\left(  a//b\right)  \right)  $ is a Bezout
pair for $\left(  a,b\right)  $.
\end{proof}

Using Lemma \ref{lem.ent.gcd.bezout0} and Lemma \ref{lem.ent.gcd.bezout-rem},
we can give a recursive algorithm for computing Bezout pairs (here implemented
in Python):
\begin{verbatim}
  def bezout_pair(a, b): # for b nonnegative
    if b == 0: # this is the trivial case
      if a >= 0:
        return (1, 0)
      if a < 0:
        return (-1, 0)
    # now to the nontrivial case (b > 0):
    (u, v) = bezout_pair(b, a%b)
    return (v, u - v * (a//b))
\end{verbatim}

In human language, this says:

\begin{itemize}
\item If $b=0$, then a Bezout pair for $\left(  a,b\right)  $ is either
$\left(  1,0\right)  $ or $\left(  -1,0\right)  $ depending on whether
$a\geq0$ or $a<0$.

\item Otherwise, replace $a$ and $b$ by $b$ and $a\%b$, then compute a Bezout
pair $\left(  u,v\right)  $ for the new $a$ and $b$, and then replace it by
$\left(  v,\ u-v\left(  a//b\right)  \right)  $ where $a$ and $b$ are again
the original $a$ and $b$ (not the new $a$ and $b$).
\end{itemize}

This algorithm is called the \textbf{extended Euclidean algorithm}. It can be
easily adapted to negative $b$ using Lemma \ref{lem.ent.gcd.bezout-b}. It is
comparably fast to the original Euclidean algorithm, but not quite as fast,
since it involves \textquotedblleft back-substitution\textquotedblright\ (the
step where $\left(  u,v\right)  $ is transformed into $\left(  v,\ u-v\left(
a//b\right)  \right)  $).

\subsubsection{The universal property of the gcd}

Consider two integers $a$ and $b$ that are not both $0$. By its definition,
$\gcd\left(  a,b\right)  $ is greater or equal to any common divisor of $a$
and $b$. But something even better is true: It is \textbf{divisible} by any
common divisor of $a$ and $b$. In other words:

\begin{proposition}
\label{prop.ent.gcd.univ1}Let $a$ and $b$ be two integers. Then, any common
divisor of $a$ and $b$ is a divisor of $\gcd\left(  a,b\right)  $.
\end{proposition}

\begin{proof}
Let $d$ be a common divisor of $a$ and $b$. We must prove that $d$ is a
divisor of $\gcd\left(  a,b\right)  $.

Bezout's theorem yields $\gcd\left(  a,b\right)  =xa+yb$ for some integers $x$
and $y$. Consider these $x$ and $y$. Both $xa$ and $yb$ are multiples of $d$
(since $d\mid a\mid xa$ and $d\mid b\mid yb$). Thus, their sum $xa+yb$ is also
a multiple of $d$ (since a sum of two multiples of $d$ is a multiple of $d$).
But this sum is $\gcd\left(  a,b\right)  $. So we have shown that $\gcd\left(
a,b\right)  $ is a multiple of $d$. In other words, $d$ is a divisor of
$\gcd\left(  a,b\right)  $. This proves Proposition \ref{prop.ent.gcd.univ1}.
\end{proof}

\begin{theorem}
[universal property of the gcd]\label{thm.entn.gcd.univ}Let $a$ and $b$ be two
integers. Then, the common divisors of $a$ and $b$ are precisely the divisors
of $\gcd\left(  a,b\right)  $.
\end{theorem}

\begin{proof}
Proposition \ref{prop.ent.gcd.univ1} shows that any common divisor of $a$ and
$b$ is a divisor of $\gcd\left(  a,b\right)  $. Conversely, any divisor $d$ of
$\gcd\left(  a,b\right)  $ is a common divisor of $a$ and $b$ (since
$d\mid\gcd\left(  a,b\right)  \mid a$ and likewise $d\mid b$). Theorem
\ref{thm.entn.gcd.univ} follows.
\end{proof}

\subsubsection{The Frobenius coin problem}

Let us return to the puzzle about $a$-cent coins and $b$-cent coins. What
denominations can you pay using these coins if you do \textbf{not} take change?

Usually, you cannot pay $\gcd\left(  a,b\right)  $ cents. For example, you
cannot pay $2$ cents with $4$-cent and $6$-cent coins. But still, you can pay
$4,6,8,10,12,\ldots$ cents.

With $3$-cent coins and $5$-cent coins, you can pay the denominations%
\[
3,\ 5,\ 6,\ \underbrace{8,\ 9,\ 10,\ 11,\ 12,\ 13,\ \ldots}_{\text{any integer
}\geq8}.
\]


How does the answer look like for arbitrary $a$ and $b$ ? (This is known as
the \textbf{Frobenius coin problem}.)

The only interesting case is when $\gcd\left(  a,b\right)  =1$, because if $a$
and $b$ have common divisors larger than $1$, then we can just factor these
divisors out.

In the case $\gcd\left(  a,b\right)  =1$, there is a nice partial answer by Sylvester:

\begin{theorem}
[Sylvester's two-coin theorem]Let $a$ and $b$ be two positive integers such
that $\gcd\left(  a,b\right)  =1$. Then:

\textbf{(a)} Any integer $n>ab-a-b$ can be written in the form
\[
n=xa+yb\ \ \ \ \ \ \ \ \ \ \text{with }x,y\text{ nonnegative integers}%
\]
(i.e., you can pay $n$ cents with $a$-cent coins and $b$-cent coins, without
having to take change).

\textbf{(b)} The integer $ab-a-b$ cannot be written in this form.

\textbf{(c)} Among the first $\left(  a-1\right)  \left(  b-1\right)  $
nonnegative integers $0,1,\ldots,ab-a-b$, exactly half can be written in the
form
\[
n=xa+yb\ \ \ \ \ \ \ \ \ \ \text{with }x,y\text{ nonnegative integers,}%
\]
while the other half cannot.

\textbf{(d)} For any integer $n$, exactly one of the two integers $n$ and
$ab-a-b-n$ can be written in this form.
\end{theorem}

\begin{proof}
See Theorem 3.8.3 in Lecture 11 of
\url{https://www.cip.ifi.lmu.de/~grinberg/t/23wd} (note: I did not actually do
this in class).
\end{proof}


\end{document}