Inaugurated by IN-SPACe
ISRO Registered Space Tutor
S3-SA4-0453
What is the Greatest Common Divisor using Prime Factorisation?
Grade Level:
Class 6
AI/ML, Data Science, Physics, Economics, Cryptography, Computer Science, Engineering
Definition
What is it?
The Greatest Common Divisor (GCD) of two or more numbers is the largest number that divides all of them without leaving a remainder. Using prime factorisation, we find the GCD by multiplying the common prime factors, each raised to the lowest power they appear in any of the numbers.
Simple Example
Quick Example
Imagine you have 12 ladoos and your friend has 18 jalebis. You want to pack them into identical small boxes, with each box having the same number of ladoos and jalebis, and no sweets left over. The largest number of sweets you can put in each box is the GCD of 12 and 18.
Worked Example
Step-by-Step
Let's find the GCD of 24 and 36 using prime factorisation.
Step 1: Find the prime factors of 24.
24 = 2 x 12
12 = 2 x 6
6 = 2 x 3
So, 24 = 2 x 2 x 2 x 3 = 2^3 x 3^1
---
Step 2: Find the prime factors of 36.
36 = 2 x 18
18 = 2 x 9
9 = 3 x 3
So, 36 = 2 x 2 x 3 x 3 = 2^2 x 3^2
---
Step 3: Identify the common prime factors. Both numbers have '2' and '3' as prime factors.
---
Step 4: For each common prime factor, choose the lowest power it appears in either factorisation.
For prime factor '2': It appears as 2^3 in 24 and 2^2 in 36. The lowest power is 2^2.
For prime factor '3': It appears as 3^1 in 24 and 3^2 in 36. The lowest power is 3^1.
---
Step 5: Multiply these lowest powers together.
GCD = 2^2 x 3^1 = (2 x 2) x 3 = 4 x 3 = 12
---
So, the GCD of 24 and 36 is 12.
Why It Matters
Understanding GCD helps in simplifying fractions, which is crucial in fields like Engineering for calculations or in Data Science for understanding proportions. It's also used in Computer Science for algorithms and even in Cryptography to secure online transactions, protecting your UPI payments!
Common Mistakes
MISTAKE: Multiplying all prime factors instead of only common ones. | CORRECTION: Only consider the prime factors that are present in the factorisation of ALL the numbers.
MISTAKE: Using the highest power of common prime factors instead of the lowest. | CORRECTION: For GCD, always pick the LOWEST power of each common prime factor.
MISTAKE: Not fully factorising numbers into their prime components. | CORRECTION: Ensure you break down each number completely until all factors are prime numbers.
Practice Questions
Try It Yourself
QUESTION: Find the GCD of 15 and 25 using prime factorisation. | ANSWER: 5
QUESTION: What is the GCD of 30, 42, and 60? | ANSWER: 6
QUESTION: Two buses depart from the same stop. Bus A returns every 18 minutes, and Bus B returns every 24 minutes. If they both left at 7 AM, what is the longest interval (in minutes) after which they will both be at the stop together again? (Hint: This is an LCM question, but find the GCD of 18 and 24 first as a step towards understanding common multiples.) | ANSWER: GCD of 18 and 24 is 6.
MCQ
Quick Quiz
Which of the following is the correct prime factorisation to find the GCD of 12 and 20?
12 = 2^2 x 3, 20 = 2^2 x 5. GCD = 2^2 x 3 x 5
12 = 2^2 x 3, 20 = 2^2 x 5. GCD = 2^2
12 = 2 x 6, 20 = 2 x 10. GCD = 2 x 2
12 = 2 x 2 x 3, 20 = 2 x 2 x 5. GCD = 2 x 2 x 3 x 5
The Correct Answer Is:
B
Option B correctly identifies the prime factorisations and then selects only the common prime factors (2) raised to their lowest power (2^2).
Real World Connection
In the Real World
Imagine a textile factory in Surat making different lengths of cloth. If they have a roll of 75 meters and another of 100 meters, and they want to cut both into the largest possible equal-sized pieces without any waste, they would use GCD. This helps them optimize material use and reduce waste.
Key Vocabulary
Key Terms
PRIME NUMBER: A whole number greater than 1 that has exactly two factors: 1 and itself. | FACTORISATION: Breaking down a number into its prime factors. | COMMON FACTOR: A number that divides two or more numbers without leaving a remainder. | EXPONENT: A small number written above and to the right of a base number, indicating how many times the base number is multiplied by itself.
What's Next
What to Learn Next
Great job learning about GCD! Next, you should explore the Least Common Multiple (LCM). It's another important concept that uses prime factorisation and helps solve different kinds of real-world problems, often alongside GCD.
