GCF and LCM Math Help

Question

I need help on how to do the GCF and LCM the fastest way. The way I currently use it is listing out the factors(prime) in a line and do it that way. I also know there is another way called the ladder method where you keep going down listing all the prime factors. My question is that if there another way to do this faster, please answer?

Answer 1

Finding the prime factors is often more time consuming than finding the GCD / LCM

But if you have the prime factorization.

$A = p_1^ap_2^bp_3^c\\ B = p_1^ip_2^jp_3^k$

The GDC takes the lowest power of each prime factor. The LCM is highest power of each prime factor.

$\gcd(A,B) = p_1^{\min(a,i)}p_2^{\min(b,j)}p_3^{\min(c,k)}\\ \text{lcm}(A,B)= p_1^{\max(a,i)}p_2^{\max(b,j)}p_3^{\max(c,k)}$

For example, Say you have 24 and 32 and want to find the GCD and LCM.

$24 = 2^3\cdot 3\\ 32 = 2^5$

As $3$ is not a factor of $32$ we could say the power of $3$ in the prime factorization equals $0$

$\gcd(24,32) = 2^3\cdot 3^0 = 8\\ \text{lcm}(24,32) = 2^5\cdot 3^1 = 96$

Answer 2

There is a method called the Euclidean algorithm that will help you find the GCD of two numbers $a$ and $b$ quite quickly.

1. Assuming $a$ is the larger of the two, divide $a$ by $b$ and note the remainder in the form $a = kb + r$. For example, if $a = 69$ and $b = 24$, $69 = 2 \times 24 + 21$.

2. Replace $a$ with $b$, and $b$ with $r$ in the above step, and repeat it. So in this case, we now divide $24$ by $21$, giving $24 = 1 \times 21 + 3$.

3. Continue to do this until you get a remainder of 0. In this case, $21 = 7 \times 3 + 0$. The last remainder value you got is the GCD - in this case, $\gcd(69, 24) = 3$.