# Formula for gcd(a,b) in terms of prime factors of a and b.

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$?

• merely, the powers sequence of the GCD is the sequence of the minima of $\alpha_i$ and $\beta_i$, even if null – user354674 Sep 7 '16 at 16:59
• @igael That does make sense. How can you prove that though? – user322548 Sep 7 '16 at 17:00
• No. gcd is smallest linear combination is absolutely not the strategy you want. gcd is the largest factor in common is definitely the strategy you do want. what is the largest factor in common to both $a = p_i^{\alpha_i}p_j^{\alpha_j}....$ and $b = p_k^{\alpha_k}p_l{\alpha_l}.....$? – fleablood Sep 7 '16 at 17:00
• I have to point out: "We'll write a=pα11pα22...pαkk and b=pβ11pβ22...pβkk by the unique factorization theorem." This isn't quite write. You wrote this as though a and b have the exact same prime factors only to different powers. You should write $a = p_1^{n_1}.....p_k^{n_k}$ and $b=q_1^{m_1}....q_j^{m_j}$ and note {p_i} and {q_l} may or may not have terms in common. – fleablood Sep 7 '16 at 17:03
• It does require more rigor but it is the rigor of applying a definition precisely. There is really nothing to "prove". It is merely a matter of applying the definition. – fleablood Sep 7 '16 at 17:05

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$?