[proofplan]
Define the candidate [greatest common divisor](/page/Greatest%20Common%20Divisor) by taking, for each prime $p_i$, the smaller exponent appearing in the prime factorisations of $a$ and $b$. We first verify directly from the exponent inequalities that this candidate divides both $a$ and $b$. Then we prove that every common divisor has no prime factors outside the list $p_1,\dots,p_r$ and has $p_i$-exponent at most $\min(\alpha_i,\beta_i)$ for each $i$. Therefore every common divisor divides the candidate, so the candidate is the greatest positive common divisor.
[/proofplan]
[step:Define the candidate divisor from the smaller prime exponents]
Define
\begin{align*}
d = \prod_{i=1}^r p_i^{\min(\alpha_i,\beta_i)}.
\end{align*}
If $r=0$, this is the empty product, so $d=1$. Since each $p_i$ is prime and each $\min(\alpha_i,\beta_i)$ is a nonnegative integer, $d \in \mathbb{N}$.
[/step]
[step:Show that the candidate divides both integers]
For each $i \in \{1,\dots,r\}$, the definition of the minimum gives
\begin{align*}
\min(\alpha_i,\beta_i) \le \alpha_i
\end{align*}
and
\begin{align*}
\min(\alpha_i,\beta_i) \le \beta_i.
\end{align*}
Hence the quotients
\begin{align*}
\frac{a}{d} = \prod_{i=1}^r p_i^{\alpha_i-\min(\alpha_i,\beta_i)}
\end{align*}
and
\begin{align*}
\frac{b}{d} = \prod_{i=1}^r p_i^{\beta_i-\min(\alpha_i,\beta_i)}
\end{align*}
are positive integers. Therefore $d \mid a$ and $d \mid b$.
[guided]
We must first check that the proposed formula actually gives a common divisor. The proposed integer is
\begin{align*}
d = \prod_{i=1}^r p_i^{\min(\alpha_i,\beta_i)}.
\end{align*}
For a fixed index $i \in \{1,\dots,r\}$, the exponent $\min(\alpha_i,\beta_i)$ is no larger than either exponent:
\begin{align*}
\min(\alpha_i,\beta_i) \le \alpha_i
\end{align*}
and
\begin{align*}
\min(\alpha_i,\beta_i) \le \beta_i.
\end{align*}
Thus the exponent differences $\alpha_i-\min(\alpha_i,\beta_i)$ and $\beta_i-\min(\alpha_i,\beta_i)$ are nonnegative integers. Dividing $a$ by $d$ subtracts exponents prime-by-prime, giving
\begin{align*}
\frac{a}{d} = \prod_{i=1}^r p_i^{\alpha_i-\min(\alpha_i,\beta_i)}.
\end{align*}
The right-hand side is a product of nonnegative powers of primes, hence is a positive integer. Therefore $d \mid a$. The same computation for $b$ gives
\begin{align*}
\frac{b}{d} = \prod_{i=1}^r p_i^{\beta_i-\min(\alpha_i,\beta_i)},
\end{align*}
again a positive integer, so $d \mid b$. This proves that $d$ is a common divisor of $a$ and $b$.
[/guided]
[/step]
[step:Bound the prime exponents of an arbitrary common divisor]
Let $c \in \mathbb{N}$ be any common divisor of $a$ and $b$. By uniqueness of prime factorisation, write
\begin{align*}
c = \prod_{j=1}^s q_j^{\gamma_j},
\end{align*}
where $s \in \mathbb{Z}_{\ge 0}$, the numbers $q_1,\dots,q_s$ are pairwise distinct primes, and $\gamma_j \in \mathbb{N}$ for each $j \in \{1,\dots,s\}$.
Since $c \mid a$, there is an integer $u \in \mathbb{N}$ such that $a=cu$. Comparing prime factors in the prime factorisations of $a$, $c$, and $u$ by uniqueness of prime factorisation, every prime $q_j$ must be one of the primes $p_1,\dots,p_r$. Moreover, if $q_j=p_i$, then the exponent of $p_i$ in $c$ is at most $\alpha_i$. Since also $c \mid b$, the same comparison with $b$ shows that the exponent of $p_i$ in $c$ is at most $\beta_i$. Therefore, for each $i \in \{1,\dots,r\}$, the exponent of $p_i$ in $c$ is at most
\begin{align*}
\min(\alpha_i,\beta_i).
\end{align*}
No prime outside $\{p_1,\dots,p_r\}$ divides $c$.
[/step]
[step:Conclude that every common divisor divides the candidate]
From the previous step, the prime factorisation of $c$ uses only primes among $p_1,\dots,p_r$, and the exponent of $p_i$ in $c$ is at most $\min(\alpha_i,\beta_i)$ for every $i$. Hence there are nonnegative integers $\delta_i \in \mathbb{Z}_{\ge 0}$ such that
\begin{align*}
c = \prod_{i=1}^r p_i^{\delta_i}
\end{align*}
and
\begin{align*}
\delta_i \le \min(\alpha_i,\beta_i)
\end{align*}
for every $i \in \{1,\dots,r\}$. Therefore
\begin{align*}
\frac{d}{c} = \prod_{i=1}^r p_i^{\min(\alpha_i,\beta_i)-\delta_i}
\end{align*}
is a positive integer, so $c \mid d$.
[/step]
[step:Identify the candidate as the greatest common divisor]
We have proved that $d$ is a positive common divisor of $a$ and $b$, and that every positive common divisor $c$ of $a$ and $b$ divides $d$. In particular, every positive common divisor $c$ satisfies $c \le d$. Hence $d$ is the greatest positive integer dividing both $a$ and $b$, which is the definition of $\gcd(a,b)$. Therefore
\begin{align*}
\gcd(a,b) = d = \prod_{i=1}^r p_i^{\min(\alpha_i,\beta_i)}.
\end{align*}
[/step]
