Solution af400b33-5c42-4f76-a10b-d4ea34d3e06c

Points: 2 pts

Lemma 1

For every $i$, we have
\[
p_i^{\min(a_i,b_i)}\mid p_i^{a_i}
\qquad\text{and}\qquad
p_i^{\min(a_i,b_i)}\mid p_i^{b_i}.
\]
Since $a_i\geq\min(a_i,b_i)$, the exponent in
\[
p_i^{a_i-\min(a_i,b_i)}
\]
is nonnegative, so this number is an integer. Thus
\[
p_i^{a_i}
= p_i^{\min(a_i,b_i)}\,p_i^{a_i-\min(a_i,b_i)}
\]
is an integer multiple of $p_i^{\min(a_i,b_i)}$. The same argument applies to $b_i$.

Lemma 2: The product is the greatest common divisor.

Let
\[
d=p_1^{\min(a_1,b_1)}p_2^{\min(a_2,b_2)}\cdots p_r^{\min(a_r,b_r)}.
\]
Multiplying the divisibility statements from Lemma 1 gives
\[
d\mid n\qquad\text{and}\qquad d\mid m.
\]
Now let $c$ be any positive common divisor of $n$ and $m$. By unique prime factorization, we can write
\[
c=p_1^{c_1}p_2^{c_2}\cdots p_r^{c_r},
\]
where the exponents are integers satisfying
\[
0\leq c_i\leq a_i\qquad\text{and}\qquad 0\leq c_i\leq b_i.
\]
Hence
\[
c_i\leq\min(a_i,b_i)
\quad\Longrightarrow\quad
p_i^{c_i}\mid p_i^{\min(a_i,b_i)}.
\]
Multiplying these statements gives $c\mid d$, so $c\leq d$. Therefore $d$ is the greatest common divisor of $n$ and $m$.

Final answer:
\gcd(n,m)=p_1^{\min(a_1,b_1)}p_2^{\min(a_2,b_2)}\cdots p_r^{\min(a_r,b_r)}