[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$.[/step]

[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: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]