Embedded Files
(Credits-Bogomolny, Alexander. “GCD and LCM via Factor Tree.” GCD and LCM via Factor Tree, www.cut-the-knot.org/Curriculum/Arithmetic/GCDByBTree.shtml. Accessed 8 June 2026.)
Divisibility Intro
Divisibility Intro
In divisibility of Number Theory, prime factorization is useful for finding the greatest common divisor, or in other words GCD, of two numbers. For example, the numbers 60 and 282 have a GCD of 2x3=6 and can be written as GCD (60,282) =2x3=6. Before we start, it is important to note that greatest common divisor, GCD, and greatest common factor, GCF, are the same thing.
Math Definition
Math Definition
In a mathematical definition, let n and m be two integers. We say n divides m if there exist a third integer q such that,
n x q=m.
In mathematical notation, we write it as n|m to indicate that n divides m. For example, 3 divides 60 because there is another integer being 20, meaning 3 x 20=60 and q=20.
Example (1): Listing the Factors:
Example (1): Listing the Factors:
For example, if we were to find gcd(24,60), we would first start off with listing all the factors of each number.
Factors of 24 are 1, 2, 3, 4, 6, 8, 12, and 24.
Factors of 60 are 1, 2, 3, 4, 5, 6, 10, 12, 15, 20, 30, and 60.
The common factors are 1, 2, 3, 4, 6, and 12. The greatest common factor is 12.
Therefore,
gcd(24,60)=12
Example (2): Prime Factorization:
Example (2): Prime Factorization:
For example, let's find the gcd(24,60) but this time we will start off by looking at their prime factorization.
24= 23 x 31
60=22 x 31 x 51
If we were to expand this and point out all the common factors we would have-
24= 2 x 2 x 2 x 3
60= 2 x 2 x 3 x 5
This points out that 24 and 60 both have two factors of 2 and one factor of 3.
Therefore,
gcd(24,60)= 2 x 2 x 3 = 12
Practice:
Practice:
(a) 5 and 15
(b) 27 and 81
(c) 121 and 99
(d) 6 and 19
Practice Answer Key:
Practice Answer Key:
(a) 5 and 15
Factors of 5 are 1 and 5
Factors of 15 are 1, 3, 5, 15
The common factors are 1 and 5.
Therefore,
gcd( 5, 15) = 1 x 5 = 5
(b) 27 and 81
Prime Factorization of 27 and 81-
27 = 3 x 3 x 3 = 33
81= 3 x 3 x 3 x 3 = 34
This shows that 27 and 81 both have three factors of 3.
Therefore,
gcd( 27 , 81) = 33 =27
(c) 121 and 99
Prime Factorization of 121 and 99-
121= 11 x 11 = 112
99= 3 x 3 x 11 = 32 x 11
This shows that 121 and 99 both have one factor of 11.
Therefore,
gcd( 121, 99) =11
(d) 6 and 19
Factors of 6 are 1, 2, 3, 6
Factors of 19 are 1 and 19
The common factor is one. 6 and 19 only share one common factor because 19 is a prime number.
Therefore,
gcd( 6, 19)= Relatively Prime (1)
Practice Answer Key Video:
Practice Answer Key Video:
DivisibilityVideo.mp4Page updated
Report abuse