Setup: Let $a,b\in\mathbb{N}$. Moreover, let $p_1,p_2,...,p_k$ be the collection of all primes which divide $a$ or $b$ or both. We'll write $a=p_1^{\alpha_1}p_2^{\alpha_2}...p_k^{\alpha_k}$ and $b=p_1^{\beta_1}p_2^{\beta_2}...p_k^{\beta_k}$ by the unique factorization theorem. Notably, some $\alpha_i$'s and some $\beta_i$'s might be $0$.
I am asked to give a formula for gcd$(a,b)$ in terms of $p_i$'s, $\alpha_i$'s, and $\beta_i$'s. Supposedly the justification for such a formula should derive from the definition of GCD.
My thoughts: the definition of GCD says that the GCD is the smallest linear combination of $a$ and $b$. In other words, $\exists u,v\in\mathbb{Z}$ such that $ua+vb=$gcd$(a,b)$. Then, simply replace $a$ and $b$ with their prime factorizations. But what do we do about $u$ and $v$?
The GCD is the biggest number that goes into both.
Look at each prime one by one and ask yourself: what is the highest power of $p$ that goes into both?
For example: let $m=421,875=2^0\cdot3^3 \cdot 5^6$ and $n=45,000=2^3\cdot 3^2\cdot 5^4$.
It's important to write both numbers as powers of the same primes. So even though $m$ is not divisible by $2$, I still included a factor of $2$, but $2^0=1$.
The highest power of $2$ that goes into both is $2^0$. The highest power of $3$ that goes into both is $3^2$. The highest power of $5$ that goes into both is $5^4$. Hence $\gcd(m,n)=2^0\cdot3^2\cdot 5^4=5,625$.
Try a few example and see if you can get a general formula.
HINT: Remember the "minimum" function $\min$ and the "maximum" function $\max$. For example $\min(1,5)=1$ and $\max(1,5)=5$.
Can you also find a formula for $\mathrm{lcm}(m,n)$?
Can you prove that $\gcd(m,n) \times \mathrm{lcm}(m,n) = m \times n$?