Ladder (or Cake) Method
When Shana McKay [1] first came across the ladder method (i.e., the upside-down cake method) for finding greatest common factors and lowest common multiples, she thought it was nothing short of complete genius. This was pretty recent, too! Both she and I love learning new methods for teaching math concepts.
Prime factoring is super cool and extremely useful in building number sense, but if the goal is to find GCF and especially LCM, this cake method makes the process so much easier.
Here is a simple video explaining the process:
On the outside of the upside down cake are all the factors the two numbers have in common. On the bottom are the “leftover” numbers. The GCF is the product of all the common factors on the left. The LCM is the product of the GCF and the “leftovers” on the bottom.
You can also use the Euclidean algorithm for finding GCF.
NOTE: The cake method is a cool way, however it could become problematic if we try to use it to find LCM for 3 (or more) numbers. Example: LCM of 8, 12, 16 – the cake method will show GCF of 4 with remaining 2, 3, 4 and student will think the LCM is 4x2x3x4=96, but in reality the LCM is 48. Because of that, the prime factorization/factor tree might be safer method. But the cake method will be good if only work with 2 numbers for GCF & LCM.
GCF
In mathematics, the greatest common factor (GCF), also known as the greatest common divisor, of two (or more) non-zero integers a and b, is the largest positive integer by which both integers can be divided. It is commonly denoted as GCF(a, b). For example, GCF(32, 256) = 32. [3]
Prime Factorization Method
There are multiple ways to find the greatest common factor of given integers. One of these involves computing the prime factorizations of each integer, determining which factors they have in common, and multiplying these factors to find the GCD. Refer to the example below.
EXAMPLE
GCF(16, 88, 104)
16 = 2 × 2 × 2 × 2
88 = 2 × 2 × 2 × 11
104 = 2 × 2 × 2 × 13
GCF(16, 88, 104) = 2 × 2 × 2 = 8
Prime factorization is only efficient for smaller integer values. Larger values would make the prime factorization of each and the determination of the common factors, far more tedious.
Euclidean Algorithm
Another method used to determine the GCF involves using the Euclidean algorithm. This method is a far more efficient method than the use of prime factorization. The Euclidean algorithm uses a division algorithm combined with the observation that the GCD of two integers can also divide their difference. The algorithm is as follows:
GCF(a, a) = a
GCF(a, b) = GCF(a-b, b), when a > b
GCF(a, b) = GCF(a, b-a), when b > a
In practice:
- Given two positive integers, a and b, where a is larger than b, subtract the smaller number b from the larger number a, to arrive at the result c.
- Continue subtracting b from a until the result c is smaller than b.
- Use b as the new large number, and subtract the final result c, repeating the same process as in Step 2 until the remainder is 0.
- Once the remainder is 0, the GCF is the remainder from the step preceding the zero result.
EXAMPLE
GCF(268442, 178296)
268442 – 178296 = 90146
178296 – 90146 = 88150
90146 – 88150 = 1996
88150 – 1996 × 44 = 326
1996 – 326 × 6 = 40
326 – 40 × 8 = 6
6 – 4 = 2
4 – 2 × 2 = 0
From the example above, it can be seen that GCF(268442, 178296) = 2. If more integers were present, the same process would be performed to find the GCF of the subsequent integer and the GCF of the previous two integers. Referring to the previous example, if instead the desired value were GCF(268442, 178296, 66888), after having found that GCF(268442, 178296) is 2, the next step would be to calculate GCF(66888, 2). In this particular case, it is clear that the GCF would also be 2, yielding the result of GCF(268442, 178296, 66888) = 2.
LCM
In mathematics, the least common multiple, also known as the lowest common multiple of two (or more) integers a and b, is the smallest positive integer that is divisible by both. It is commonly denoted as LCM(a, b). [2]
Brute Force Method
There are multiple ways to find a least common multiple. The most basic is simply using a “brute force” method that lists out each integer’s multiples.
EXAMPLE
Find LCM(18, 26)
18: 18, 36, 54, 72, 90, 108, 126, 144, 162, 180, 198, 216, 234
26: 52, 78, 104, 130, 156, 182, 208, 234
As can be seen, this method can be fairly tedious, and is far from ideal.
Prime Factorization Method
A more systematic way to find the LCM of some given integers is to use prime factorization. Prime factorization involves breaking down each of the numbers being compared into its product of prime numbers. The LCM is then determined by multiplying the highest power of each prime number together. Note that computing the LCM this way, while more efficient than using the “brute force” method, is still limited to smaller numbers. Refer to the example below for clarification on how to use prime factorization to determine the LCM.
EXAMPLE
Find LCM(21, 14, 38)
21 = 3 × 7
14 = 2 × 7
38 = 2 × 19
The LCM is therefore:
3 × 7 × 2 × 19 = 798
Greatest Common Divisor Method
A third viable method for finding the LCM of some given integers is using the greatest common divisor. This is also frequently referred to as the greatest common factor (GCF), among other names. Refer to the link for details on how to determine the greatest common divisor. Given LCM(a, b), the procedure for finding the LCM using GCF is to divide the product of the numbers a and b by their GCF, i.e. (a × b)/GCF(a,b). When trying to determine the LCM of more than two numbers, for example LCM(a, b, c) find the LCM of a and b where the result will be q. Then find the LCM of c and q. The result will be the LCM of all three numbers. Using the previous example.
EXAMPLE
Find LCM(21, 14, 38)
GCF(14, 38) = 2
LCM(14, 38) = 38 × 142 = 266
GCF(266, 21) = 7
LCM(266, 21) = 266 × 217 = 798
LCM(21, 14, 38) = 798
Note that it is not important which LCM is calculated first as long as all the numbers are used, and the method is followed accurately. Depending on the particular situation, each method has its own merits, and the user can decide which method to pursue at their own discretion.
Slides
Please wait for the Google Slides to load.
Download the PDF version of the slides.
References
[1] “Finding GCF and LCM with the Ladder (or Cake) Method.” 2024. Scaffolded Math and Science. Accessed February 27. https://www.scaffoldedmath.com/2019/02/finding-gcf-and-lcm-with-upside-down-cake-method.html.
[2] “Least Common Multiple Calculator.” 2024. Calculator.Net. Accessed August 31. https://www.calculator.net/lcm-calculator.html.
[3] “Greatest Common Factor Calculator.” 2024. Calculator.Net. Accessed August 31. https://www.calculator.net/gcf-calculator.html.
Additional Reading
“4.3: Least Common Multiple.” 2023. Mathematics LibreTexts. Libretexts. June 28. https://math.libretexts.org/Courses/Mount_Royal_University/Higher_Arithmetic/4:_Greatest_Common_Divisor_least_common_multiple_and_Euclidean_Algorithm/4.3:_Least_Common_Multiple.
CalculatorSoup, LLC. 2023. “Euclid’s Algorithm Calculator.” CalculatorSoup. October 18. https://www.calculatorsoup.com/calculators/math/gcf-euclids-algorithm.php.
How to Find the GCF Using Euclid’s Algorithm
a) Given two whole numbers where a is greater than b, do the division a ÷ b = c with remainder R.
b) Replace a with b, replace b with R and repeat the division.
c) Repeat step 2 until R=0.
d) When R=0, the divisor, b, in the last equation is the greatest common factor, GCF.
Since greatest common factor (GCF) and greatest common divisor (GCD) are synonymous, the Euclidean Algorithm process also works to find the GCD.
“Finding Greatest Common Factors with the Euclidean Algorithm.” 2024. Scaffolded Math and Science. Accessed February 29. https://www.scaffoldedmath.com/2018/02/euclidean-algorithm.html.
“GCF (Greatest Common Factor) – How to Find GCF? Examples.” 2024. CUEMATH. Accessed August 31. https://www.cuemath.com/numbers/gcf-greatest-common-factor/.
“Greatest Common Factor (GCF) – Definition, Procedure, Examples.” 2020. BYJUS. BYJU’S. May 15. https://byjus.com/maths/gcf/.
“Greatest Common Factor.” 2024. Math Is Fun. Accessed August 31. https://www.mathsisfun.com/greatest-common-factor.html.
“Least Common Multiple.” 2024. Math Is Fun. Accessed August 31. https://www.mathsisfun.com/least-common-multiple.html.
“The Euclidean Algorithm (Article).” 2024. Khan Academy. Khan Academy. Accessed February 28. https://www.khanacademy.org/computing/computer-science/cryptography/modarithmetic/a/the-euclidean-algorithm.
The Euclidean Algorithm for finding GCD(A,B) is as follows:
a) If A = 0 then GCD(A,B)=B, since the GCD(0,B)=B, and we can stop.
b) If B = 0 then GCD(A,B)=A, since the GCD(A,0)=A, and we can stop.
c) Write A in quotient remainder form (A = B⋅Q + R)
d) Find GCD(B,R) using the Euclidean Algorithm since GCD(A,B) = GCD(B,R)
“What Is the Greatest Common Factor and Least Common Multiple?” 2024. Mometrix Test Preparation. https://www.mometrix.com/academy/greatest-common-factor/.
Videos
The featured image on this page is from the Scaffolded Math and Science website.
Mathematical Mysteries 