\subsection{Euclidean division}\label{subsec:euclidean_division}

\begin{definition}\label{def:commutative_ring_division}
  Let \( a, b \in R \). We say that \( b \) is a \term{divisor} of \( a \) or that \( a \) is a \term{factor} of \( b \) and write \( b \mid a \) if there exists \( c \in R \) such that \( a = bc \).

  We say that \( b \) is a \term{trivial} divisor of \( a \) if \( a = bc \) and either \( b \) or \( c \) is invertible.
\end{definition}

\begin{definition}\label{def:modulo}
  Fix an ideal \( I \) of \( R \).

  If for some \( a, b \in R \) we have \( a - b \in I \), we say that \( a \) and \( b \) are \term{congruent modulo} \( I \) and write
  \begin{equation*}
    a \cong b \pmod I.
  \end{equation*}

  If the ideal \( I \) is generated by the single element \( n \) and if \( a = b \mod I \), we say that \( a \) and \( b \) are congruent modulo \( n \) and write
  \begin{equation*}
    a \cong b \pmod n.
  \end{equation*}
\end{definition}

\begin{definition}\label{def:greatest_common_denominator}
  The \term{greatest common denominator}  of \( a \) and \( b \) is defined, if it exists and is unique, as
  \begin{equation*}
    \gcd(a, b) \coloneqq \max_{\cdot \mid \cdot} \{ c \in R : c \mid a \wedge c \mid b \},
  \end{equation*}
  where the maximum is taken with respect to the divisibility partial order.
\end{definition}

\begin{definition}\label{def:factorization_in_ring}
  A factorization of \( x \in R \) is a finite sequence \( p_1, \ldots, p_n \) of \hyperref[def:irreducible_ring_element]{irreducible} elements with multiplicities \( k_1, \ldots, k_n \), so that
  \begin{equation*}
    x = e p_1^{k_1} p_2^{k_2} \cdots p_n^{k_n},
  \end{equation*}
  where \( e \) is a unit in \( R \).
\end{definition}

\begin{definition}\label{def:euclidean_domain}\mcite{nLab:euclidean_domain}
  Let \( R \) be an integral \hyperref[def:semiring/integral_domain]{domain}. Multiplication is not invertible in general, but we can instead define \term{Euclidean division} with remainders.

  We endow \( R \) with an additional function \( \delta: R \to \BbbZ_{\geq 0} \). Let \( a, b \in R \). If there exists a pair \( (q, r) \) such that
  \begin{equation*}
    a = bq + r
  \end{equation*}
  holds and either \( r = 0 \) or \( \delta(r) < \delta(b) \), we say that \( (R, \delta) \) is an \term{Euclidean domain}.

  We say that \( b \) \term{divides} \( a \) with \term{quotient} \( q \) and \term{remainder} \( r \).

  If the pair \( (q, r) \) is unique, we use the special notation
  \begin{balign*}
    q & = \quot(a, b),                    \\
    r & = \rem(a, b) = a - b \quot(a, b).
  \end{balign*}
\end{definition}

\begin{algorithm}\label{alg:euclidean_algorithm}
  Let \( R \) be an Euclidean domain. Fix \( a, b \in R \) with \( b \neq 0 \). The \term{Euclidean algorithm} for finding \( \gcd(a, b) \) proceeds as follows:
  \begin{thmenum}
    \thmitem{alg:euclidean_algorithm/initialization} Define \( r_0 \coloneqq a \) and \( r_1 \coloneqq b \).
    \thmitem{alg:euclidean_algorithm/step} Starting with \( i = 2 \), obtain \( q_i \) and \( r_i \) from \hyperref[def:semiring/euclidean_domain]{division}
    \begin{equation*}
      r_{i-2} = r_{i-1} q_i + r_i.
    \end{equation*}

    If \( r_i = 0 \), halt the algorithm with result \( \gcd(a, b) = r_i \).

    Otherwise, proceed by incrementing \( i \) and repeating this step.
  \end{thmenum}
\end{algorithm}
\begin{proof}
  Euclidean division ensures that \( \delta(r_i) < \delta(r_{i-1}) \) on every step. Thus, the algorithm terminates at some point. Denote by \( n \) the (minimum) number of steps necessary to obtain \( r_n = 0 \).

  We show by induction on \( k < n \) that \( r_n \) divides \( r_{n-k} \). The case \( k = 0 \) is obvious since \( r_n \) divides itself.

  Assume that \( r_n \) divides \( r_{n-i} \) for \( 0 < i < k \). Now since
  \begin{equation*}
    r_{n-k} = r_{n-(k-1)} q_{n-(k-2)} + r_{n-(k-2)}
  \end{equation*}
  and both of the terms on the right-hand side are factors of \( r_n \), the left-hand side \( r_{n-k} \) is also a factor.

  We conclude that \( r_n \) divides both \( r_{n-(n-1)} = r_1 = b \) and \( r_{n-n} = r_0 = a \).

  Furthermore, \( r_n \) is the greatest common divisor of \( a \) and \( b \). Indeed, assume that there exists \( d \in R \) such that \( r_n \mid d \) and both \( d \mid a \) and \( d \mid b \) hold. But he have
  \begin{equation*}
    a = b q_2 + r_2,
  \end{equation*}
  hence \( d \mid r_2 \). Proceeding by induction, we obtain that \( d \mid r_n \). But we assumed that \( r_n \mid d \), therefore \( r_n = d \) and \( r_n \) is the greatest common divisor of \( a \) and \( b \).
\end{proof}

\begin{proposition}\label{thm:euclidean_domain_is_pid}
  Every Euclidean \hyperref[def:semiring/euclidean_domain]{domain} is a principal ideal \hyperref[def:semiring/principal_ideal_domain]{domain}.
\end{proposition}
\begin{proof}
  Fix an ideal \( I \) of the Euclidean domain \( R \). By \fullref{thm:natural_numbers_are_well_ordered}, the set \( \delta(I) \) has a minimum. Choose an element \( m \in I \) such that \( \delta(m) = \min \delta(I) \). We will prove that \( I = \braket m \).

  Let \( x \in I \). We divide it by \( m \) to obtain
  \begin{equation*}
    x = mq + r,
  \end{equation*}
  such that either \( r = 0 \) or \( \delta(r) < \delta(m) \). Since both \( x \) and \( m \) are in \( I \), we have \( r = mq - x \in I \). But \( m \) minimizes \( \delta \) over \( I \), thus \( \delta(m) \leq \delta(r) \), which contradicts \( \delta(r) < \delta(m) \). Therefore, \( r = 0 \) and
  \begin{equation*}
    x = mq,
  \end{equation*}
  which implies that \( x \in \braket m \). This proves \( I \subseteq \braket m \).

  Let \( x \in \braket m \), that is, \( x = mq \) for some \( q \in R \). Since \( I \) is an ideal and \( m \in I \), all multiples of \( m \) are in \( I \) and thus \( x \in I \). This proves \( \braket m \subseteq I \).

  We have now obtained \( \braket m = I \). Since \( I \) was an arbitrary ideal, we conclude that every ideal in \( R \) is principal.
\end{proof}

\begin{proposition}\label{thm:pid_is_ufd}
  Every principal ideal \hyperref[def:semiring/principal_ideal_domain]{domain} is a unique factorization \hyperref[def:semiring/unique_factorization_domain]{domain}.
\end{proposition}

\begin{theorem}[Bezout's identity]\label{thm:bezout_identity}
  Let \( R \) be a principal ideal domain. Let \( a, b \in R \) with \( b \neq 0 \). Then \( \gcd(a, b) \) exists and, furthermore, there exist \( x, y \) such that
  \begin{equation*}
    ax + by = \gcd(a, b).
  \end{equation*}
\end{theorem}
\begin{proof}
  We will first prove the existence of \( \gcd(a, b) \). Define the ideal
  \begin{equation*}
    I \coloneqq \braket{a, b}.
  \end{equation*}

  Since every ideal is principal, there exists \( g \in I \) such that \( I = \braket g \). Let \( x, y \in R \) such that
  \begin{equation*}
    g = ax + by.
  \end{equation*}

  Note that \( g \) is a divisor of both \( a \) and \( b \) because \( a \in I \) and \( b \in I \). We will show that it is the greatest divisor. Let \( d \) be another divisor of both \( a \) and \( b \) such that \( g \mid d \) (or, equivalently, \( d \in \braket g \)).

  Let \( a = da' \) and \( b = db' \). We have
  \begin{equation*}
    g = ax + by = d(a'x + b'y),
  \end{equation*}
  which implies that \( d \mid g \). Thus, \( g = d \) and \( g \) is a greatest common denominator.
\end{proof}

\begin{algorithm}\label{alg:extended_euclidean_algorithm}
  Let \( R \) be an Euclidean domain. Fix \( a, b \in R \) with \( b \neq 0 \). We will explicitly find \( x \) and \( y \), so that \fullref{thm:bezout_identity} is satisfied:
  \begin{equation*}
    \gcd(a, b) = ax + by.
  \end{equation*}

  Let \( r_0, r_1, \ldots, r_n \) be the sequence of remainders from \fullref{alg:euclidean_algorithm}. The \term{extended Euclidean algorithm} proceeds as follows:

  \begin{thmenum}
    \thmitem{alg:extended_euclidean_algorithm/initialization} For \( i = 2 \), define
    \begin{balign*}
      x_2 & \coloneqq 1,    \\
      y_2 & \coloneqq -q_2.
    \end{balign*}

    \thmitem{alg:extended_euclidean_algorithm/step} For \( i = 2, \ldots, n \), define
    \begin{balign*}
      x_i & \coloneqq x_{i-2} - x_{i-1} q_i, \\
      y_i & \coloneqq y_{i-2} - y_{i-1} q_i.
    \end{balign*}

    \thmitem{alg:extended_euclidean_algorithm/completion} Halt the algorithm with result
    \begin{balign*}
      x & \coloneqq x_n, \\
      y & \coloneqq y_n.
    \end{balign*}
  \end{thmenum}
\end{algorithm}
\begin{proof}
  We will prove with induction on \( i = 2, \ldots, n \) that
  \begin{equation*}
    r_i = ax_i + by_i.
  \end{equation*}

  \begin{refenum}
    \refitem{alg:extended_euclidean_algorithm/initialization} For \( i = 2 \), we have
    \begin{balign*}
      r_0       & = r_1 q_2 + r_2, \\
      a         & = b q_2 + r_2,   \\
      a - b q_2 & = r_2,
    \end{balign*}
    that is, \( r_2 = a + b (-q_2) \).

    \refitem{alg:extended_euclidean_algorithm/step} For \( i = 3, \ldots, n \), we have
    \begin{balign*}
      r_{i-2}                                               & = r_{i-1} q_i + r_i,                 \\
      a x_{i-2} + b y_{i-2}                                 & = (a x_{i-1} + b y_{i-1}) q_i + r_i, \\
      a (x_{i-2} - x_{i-1} q_i) + b (y_{i-2} - y_{i-1} q_i) & = r_i.
    \end{balign*}

    \refitem{alg:extended_euclidean_algorithm/completion} Since \( r_n = \gcd(a, b) \), we conclude that
    \begin{equation*}
      \gcd(a, b) = a x_n + b y_n.
    \end{equation*}
  \end{refenum}
\end{proof}
