Computing GCD and LCM with Prime Factorization

GCD and LCM stand for greatest common divisor and least common multiple, respectively. The GCD for a set of numbers is largest number such that all the numbers in the set are divisible by it. The LCM is the lowest number such that it is divisible by all the numbers in the set, that are being compared.

For example, the GCD of $15$ and $10$ is $5$, because $5$ is the largest number that both $15$ and $10$ are divisible by.

As for LCM, the LCM Of $15$ and $10$ is $30$, because $30$ is the lowest number that is divisible by both $15$ and $10$.

One way of computing GCD and LCM is through prime factorization. Calculating LCM through prime factorization was covered in a different explanation (which can be found here).

Example for explanation: Find the GCD of $12$, $14$, and $8$. First, we need to factorize each number into its primes.

$12 = 2^2*3$, $14=2*7$, and $8=2^3$

Now we have to check between the numbers and see which factors are common. The greatest power of $2$ that all $3$ numbers have is $2^1$. As for $3$, $12$ has a factor of $3$, but $14$ and $8$ do not. Similarly, $14$ has a factor of $7$, but $12$ and $8$ do not. Thus, the GCD of $12$, $14$, and $8$ is $2$.

Try these problems:

Note that if the GCD between two numbers is $1$, they are relatively prime (more on relatively prime here).

We've seen a lot of factoring rules and proofs for small numbers, but what about factoring rules for any number? What's the rule for $7$? $13$? $617$?

One fun thing we can do is derive rules for any number based on a very simple piece of information about it: when is this number exactly $1$ away from a multiple of $10$?

We can start this off with an example and then look back and justify each step that we make. This may require some additional knowledge of variables and exponents.

First, we need to find a way to represent any number that we want to check for divisibility. One way to do this is to look at powers of $10$: any number is the sum of its ones digit, $10$ times its tens digit, $100$ times its hundreds digit, and so on. In summation notation, this is $10^na_n + ... + 10^2a_2 + 10^1a_1 + 10^0a_0$, where $a_n$ is the digit at the $n^{th}$ place.

For example, the number $128$ is $100+20+8=10^2\times 1+10^1\times 2 +10^0\times 8$, so $a_0$ would be $8$, $a_1$ would be $2$, and $a_2$ would be $1$.

Now, let's look at any number of this form. We can make a few specific (seemingly useless) adjustments to the number. $$10^na_n + ... + 10^2a_2 + 10^1a_1 + 10^0a_0$$ Suppose we want this number to be divisible by $17$. This means that we can rewrite it as $$10^na_n + ... + 10^2a_2 + 10^1a_1 + 10^0a_0=17k$$ for some number $k$.

We saw before that $51$ is a multiple of $17$ that is $1$ away from a multiple of $10$, so let's try using that fact here: $$10^na_n + ... + 10^2a_2 + 10^1a_1 + 10^0a_0 + 51 a_0 - 51 a_0 = 17k$$ This step may seem a little weird, but it's perfectly legal. Recall that $10^0=1$. Let's continue by combining some terms: $$10^na_n + ... + 10^2a_2 + 10^1a_1 - 50 a_0 10^0 + 51 a_0=17k$$ This form is pretty interesting because we can factor out a $10$ from most of the terms: $$10( 10^{n-1} a_n + ... + 10^1 a_2 + a_1 - 5 a_0) + 51 a_0=17k$$ $51 a_1$ is definitely divisible by $17$, so we know that $10(10^{n-1} a_n + ... + 10^1 a_2 + a_1 - 5 a_0)$ must also be divisible by $17$.

Amazingly, the form $10( 10^{n-1} a_n + ... + 10^1 a_2 + a_1 - 5 a_0)$ is actually enough to get us a divisibility rule! Let's unpack the definition: $$\color{red}{10( 10^{n-1} a_n + ... + 10^1 a_2 + a_1} \color{blue}{- 5 a_0)}$$ The part in red does not include an $a_0$ term; this is analogous to taking a number, removing its ones digit, and shifting the rest of the numbers down one place. More concretely, it's like dividing a number by $10$ and not looking at what's after the decimal point. The part in blue is the ones digit of the original number. In fact, it represents subtracting five times the original ones digit from the new, red number.

We can put this together to get the following divisibility rule for $17$: A number is divisible by $17$ if you can take the last digit, subtract five times that digit from the remaining number, and still end up with a multiple of $17$.

For example, $6{,}239 \rightarrow 623 - 5\times 9 = 578 \rightarrow 57 - 5\times 8 =17$. The last number we get, $17$, is divisible by $7$, so the original number ($6{,}239$) was also divisible by $17$.

Greatest common divisor/factor (gcd) of two numbers $m,n$ is the greatest number that divides both $m$ and $n$.

Least common multiple (lcm) of two numbers $m,n$ is the least positive integer number that is divisible by both $m$ and $n$.

(Why don't we define least common divisor or greatest common multiple? )

Michael Yang's post has shown how to calculate gcd/lcm with prime factorisation. This explanation will give a generalisation for gcd/lcm with prime factorisation.

Let's say we consider two positive integers $m,n$ with unique prime factorisation $m=p_1^{\alpha_1} \cdots p_k^{\alpha_k}$ and $n=p_1^{\beta_1}p_2^{\beta_2} \cdots p_k^{\beta_k}$ with $\alpha_i,\beta_i \ge 0, i=1,2, \cdots ,k$. Then what can $\gcd (m,n)$ be equal to ? (Let $\gcd (m,n)=G$ for convenience).

One way to to try all numbers from $1$ to $\min \{ m,n \}$ and pick the greatest number that divides both $m$ and $n$. Another way to look at it is consider a prime factor $p_1$, if $G=p_1^x \cdot y$ with $p_1 \nmid y$ and $x< \min \{ \alpha_1,\alpha_2 \}$ then of course $Gp_1$ is also divisor of $m,n$. We note that $G<Gp_1$ which contradicts to our greatest condition of $G$. Thus, that means $x \ge \min \{ \alpha_1, \beta_1 \}$. Since $x$ can't be greater than $\min \{ \alpha_1, \beta_1 \}$ (why?) so $x= \min \{ \alpha_1, \beta_1 \}$.

We do the similar thing to other prime divisor $p_i$. After all, we will obtain $$\gcd (m,n)= p_1^{\min \{ \alpha_1, \beta_1 \}} \cdots p_k^{\min \{ \alpha_k,\beta_k \}}.$$ This is the general formula to find gcd based on prime factorisation. Similarly, what is $\text{lcm} (m,n)$?

It is $$\text{lcm}(m,n)= p_1^{\max \{ \alpha_1, \beta_1 \} } \cdots p_k^{\max \{ \alpha_1, \beta_1 \} }.$$ Now, we can easily find gcd/lcm of any two numbers. What else can this formula be used for? It can be used to prove the following interesting fact: $$mn=\gcd (m,n) \cdot \text{lcm} (m,n),$$ which you can see the proof in here.

Now, we know to compute $\gcd (m,n), \text{lcm} (m,n)$, but what about lcm/gcd of some $k$ numbers? The idea is similar when computing with $2$ numbers: If $m_i=p_1^{\alpha_{1i}} \cdots p_k^{\alpha_{ki}},i= 1,2, \ldots,s$ then $$\gcd (a_1, \ldots, m_s)=p_1^{\min (\alpha_{11},\alpha_{12}, \ldots, \alpha_{1s})} \cdots p_k^{\min (\alpha_{k1},\alpha_{k2}, \ldots, \alpha_{ks})}.$$

Let $a,b,c$ be positive integers. Prove that $$\gcd (a,b,c)= \gcd (a, \gcd (b,c))= \gcd (\gcd (a,b), \gcd (b,c)).$$

Problem: Let $a,b,c$ be positive integers. Prove that $$\gcd (a,b,c)= \gcd (a, \gcd (b,c))= \gcd (\gcd (a,b), \gcd (b,c)).$$

Solution: Use prime factorisation.