[proofplan] We prove that the positive common divisors of $a$ and $b$ are exactly the positive common divisors of $b$ and $r$. The identity $a = qb + r$ gives $r = a - qb$, so any divisor of both $a$ and $b$ divides $r$. Conversely, the same identity shows that any divisor of both $b$ and $r$ divides $a$. Since the two pairs have the same positive common divisors, their greatest elements, namely their greatest common divisors, are equal. [/proofplan] [step:Show that every positive common divisor of $a$ and $b$ also divides $r$] Let $d \in \mathbb{Z}_{>0}$ be a positive common divisor of $a$ and $b$. By the definition of divisibility in $\mathbb{Z}$, there exist $m,n \in \mathbb{Z}$ such that \begin{align*} a = dm \end{align*} and \begin{align*} b = dn. \end{align*} Define $s \in \mathbb{Z}$ by $s = m - qn$. Since $q,n,m \in \mathbb{Z}$, we have $s \in \mathbb{Z}$. Using $a = qb + r$, we get \begin{align*} r = a - qb. \end{align*} Substituting $a = dm$ and $b = dn$ gives \begin{align*} r = dm - qdn. \end{align*} Factoring out $d$ gives \begin{align*} r = d(m - qn) = ds. \end{align*} Thus $d \mid r$. Since $d \mid b$ by assumption, $d$ is a positive common divisor of $b$ and $r$. [guided] Let $d \in \mathbb{Z}_{>0}$ be a positive common divisor of $a$ and $b$. This means precisely that $d \mid a$ and $d \mid b$. By the definition of divisibility in the integers, there are integers $m,n \in \mathbb{Z}$ such that \begin{align*} a = dm \end{align*} and \begin{align*} b = dn. \end{align*} The relation $a = qb + r$ should be read as a way to express $r$ as an integer linear combination of $a$ and $b$. Rearranging gives \begin{align*} r = a - qb. \end{align*} Substitute the divisibility representations of $a$ and $b$: \begin{align*} r = dm - qdn. \end{align*} Now define $s \in \mathbb{Z}$ by \begin{align*} s = m - qn. \end{align*} This is an integer because $m,q,n \in \mathbb{Z}$ and the integers are closed under multiplication and subtraction. Therefore \begin{align*} r = d(m - qn) = ds. \end{align*} By the definition of divisibility, $d \mid r$. Since $d \mid b$ was already part of the assumption, $d$ is a positive common divisor of $b$ and $r$. [/guided] [/step] [step:Show that every positive common divisor of $b$ and $r$ also divides $a$] Let $d \in \mathbb{Z}_{>0}$ be a positive common divisor of $b$ and $r$. By the definition of divisibility in $\mathbb{Z}$, there exist $n,t \in \mathbb{Z}$ such that \begin{align*} b = dn \end{align*} and \begin{align*} r = dt. \end{align*} Define $u \in \mathbb{Z}$ by $u = qn + t$. Since $q,n,t \in \mathbb{Z}$, we have $u \in \mathbb{Z}$. Using $a = qb + r$, we obtain \begin{align*} a = qdn + dt. \end{align*} Factoring out $d$ gives \begin{align*} a = d(qn + t) = du. \end{align*} Thus $d \mid a$. Since $d \mid b$ by assumption, $d$ is a positive common divisor of $a$ and $b$. [/step] [step:Identify the two greatest common divisors from the equality of common divisor sets] Define the set $C_{a,b} \subset \mathbb{Z}_{>0}$ of positive common divisors of $a$ and $b$ by \begin{align*} C_{a,b} = \{d \in \mathbb{Z}_{>0} : d \mid a \text{ and } d \mid b\}. \end{align*} Define the set $C_{b,r} \subset \mathbb{Z}_{>0}$ of positive common divisors of $b$ and $r$ by \begin{align*} C_{b,r} = \{d \in \mathbb{Z}_{>0} : d \mid b \text{ and } d \mid r\}. \end{align*} The first step proves $C_{a,b} \subset C_{b,r}$, and the second step proves $C_{b,r} \subset C_{a,b}$. Hence \begin{align*} C_{a,b} = C_{b,r}. \end{align*} Because $b \ne 0$, neither pair $(a,b)$ nor $(b,r)$ is the zero pair, so both greatest common divisors are defined. By the definition of $\gcd(a,b)$ as the greatest element of $C_{a,b}$ and $\gcd(b,r)$ as the greatest element of $C_{b,r}$, the equality of the two sets gives \begin{align*} \gcd(a,b) = \gcd(b,r). \end{align*} This proves the Euclidean step for the [greatest common divisor](/page/Greatest%20Common%20Divisor). [/step]