GCD and LCM
60 flashcards covering GCD and LCM for the GMAT Quantitative section.
GCD, or Greatest Common Divisor, is the largest number that divides evenly into two or more integers without a remainder. For instance, the GCD of 8 and 12 is 4, as it's the biggest number that splits both evenly. Meanwhile, LCM, or Least Common Multiple, is the smallest number that both integers can multiply into; for 8 and 12, it's 24. These concepts help simplify fractions, compare quantities, and solve problems involving shared factors, forming a basic building block in math.
On the GMAT Quantitative section, GCD and LCM appear in word problems, data sufficiency, or algebra questions that require simplifying expressions or finding common multiples and divisors. Common traps include confusing the two concepts or misapplying them to non-prime numbers, leading to errors in ratios or fractions. Focus on practicing quick calculations and recognizing relationships, like how GCD and LCM connect through the product of the numbers.
A concrete tip: Always double-check by listing factors for small numbers to build confidence.
Terms (60)
- 01
Greatest Common Divisor
The greatest common divisor of two or more integers is the largest positive integer that divides each of the integers without leaving a remainder.
- 02
Least Common Multiple
The least common multiple of two or more integers is the smallest positive integer that is divisible by each of the integers.
- 03
Prime Factorization
Prime factorization is the process of breaking down a composite number into its smallest prime factors, which is essential for calculating GCD and LCM.
- 04
Euclidean Algorithm
The Euclidean algorithm is a method to find the GCD of two numbers by repeatedly dividing and taking remainders until the remainder is zero; the last non-zero remainder is the GCD.
- 05
Formula for LCM of Two Numbers
The formula for the least common multiple of two numbers a and b is LCM(a, b) = (a b) / GCD(a, b), where a and b are positive integers.
- 06
Relationship Between GCD and LCM
For any two positive integers a and b, the product of the numbers equals the product of their GCD and LCM, expressed as a b = GCD(a, b) LCM(a, b).
- 07
Coprime Numbers
Two numbers are coprime if their GCD is 1, meaning they share no common positive integer factors except for 1.
- 08
GCD of Two Numbers
To find the GCD of two numbers, list their factors and identify the largest common factor, or use prime factorization to compare shared prime factors.
- 09
LCM of Two Numbers
To find the LCM of two numbers, take the highest power of each prime that appears in their prime factorizations and multiply them together.
- 10
GCD of Three Numbers
The GCD of three numbers is the largest positive integer that divides all three without a remainder, found by first calculating the GCD of the first two and then with the third.
- 11
LCM of Three Numbers
The LCM of three numbers is the smallest number that is a multiple of all three, calculated by finding the LCM of the first two and then with the third.
- 12
Properties of GCD
GCD has properties such as GCD(a, a) equals a, and GCD(a, 1) equals 1, making it useful for simplifying expressions and solving divisibility problems.
- 13
Properties of LCM
LCM properties include that it is always at least as large as the largest number involved, and it helps in finding common denominators for fractions.
- 14
Common Divisors
Common divisors of two numbers are the integers that divide both without a remainder, with the greatest one being the GCD.
- 15
Common Multiples
Common multiples of two numbers are the integers that are multiples of both, with the least one being the LCM.
- 16
Factors of a Number
Factors of a number are the integers that divide it evenly, and identifying them is key to determining GCD.
- 17
Multiples of a Number
Multiples of a number are the results of multiplying it by integers, and the smallest common multiple is used for LCM calculations.
- 18
Simplifying Fractions Using GCD
To simplify a fraction, divide both the numerator and denominator by their GCD to reduce it to its lowest terms.
- 19
Adding Fractions Using LCM
To add fractions, find a common denominator using the LCM of the denominators, then add the numerators accordingly.
- 20
Word Problems Involving GCD
In word problems, GCD is used to find the largest quantity that divides evenly into given amounts, such as in sharing items equally.
- 21
Word Problems Involving LCM
In word problems, LCM helps determine the smallest time or quantity that satisfies multiple conditions, like meeting schedules.
- 22
Example: GCD of 24 and 36
The GCD of 24 and 36 is 12, as it is the largest number that divides both evenly.
Prime factors: 24 = 2^3 3, 36 = 2^2 3^2, so GCD = 2^2 3 = 4 3 = 12.
- 23
Example: LCM of 5 and 7
The LCM of 5 and 7 is 35, since they are both prime and have no common factors other than 1.
Multiples of 5: 5, 10, 15, 20, 25, 30, 35; multiples of 7: 7, 14, 21, 28, 35.
- 24
Strategy for GCD Problems
For GCD problems on the GMAT, quickly list factors or use the Euclidean algorithm to efficiently find the greatest common divisor.
- 25
Strategy for LCM Problems
For LCM problems, use prime factorization to identify the highest powers of primes, ensuring you capture all necessary multiples.
- 26
GCD and Even/Odd Numbers
If one number is even and the other odd, their GCD must be odd, as even numbers introduce factors of 2 that odd numbers lack.
- 27
LCM and Prime Numbers
The LCM of prime numbers is their product if they are distinct, since primes have no common factors.
- 28
Distributive Property with GCD
GCD distributes over addition in certain cases, such as GCD(a, b + c) being a factor if a divides b and c, but verify with specific numbers.
- 29
Calculating GCD Manually
To calculate GCD manually, repeatedly apply the division algorithm until the remainder is zero, as in the Euclidean method.
- 30
Calculating LCM Manually
To calculate LCM manually, list multiples of the larger number until you find one that is also a multiple of the smaller number.
- 31
GCD in Division Algorithm
The division algorithm underpins GCD calculations, stating that for integers a and b, a can be expressed as a = bq + r, where r is the remainder.
- 32
LCM in Least Common Denominator
LCM is used as the least common denominator when adding or subtracting fractions with different denominators.
- 33
Trap: Confusing GCD with LCM
A common trap is mixing up GCD, which is the largest shared factor, with LCM, which is the smallest shared multiple, leading to incorrect answers.
- 34
Trap: Incorrect Prime Factorization
An error in prime factorization, such as missing a factor, can lead to wrong GCD or LCM results, so double-check each step.
- 35
Advanced: GCD of More Than Three Numbers
For more than three numbers, calculate GCD iteratively, such as GCD(a, b, c, d) = GCD(GCD(a, b, c), d).
- 36
Advanced: LCM of Non-Coprime Numbers
For non-coprime numbers, LCM accounts for shared factors by taking the highest powers, unlike for coprime numbers where it's just the product.
- 37
Formula: GCD of Three Numbers
The GCD of three numbers a, b, and c can be found using GCD(a, b, c) = GCD(GCD(a, b), c), extending the pairwise method.
- 38
Formula: LCM of Three Numbers
The LCM of three numbers a, b, and c is LCM(a, b, c) = LCM(LCM(a, b), c), building on the two-number formula.
- 39
Application: GCD in Ratios
In ratios, GCD simplifies the ratio by dividing each term by their common divisor, making it easier to compare proportions.
- 40
Application: LCM in Proportions
LCM helps in proportions by finding a common multiple for scaling, such as in mixture or rate problems.
- 41
Example: GCD in Simplifying Ratios
To simplify the ratio 15:25, use GCD of 15 and 25, which is 5, to get 3:5.
÷ 5 = 3, 25 ÷ 5 = 5.
- 42
Example: LCM in Scheduling Problems
In scheduling, LCM of 4 and 6 days is 12 days, meaning events repeat every 12 days.
A task every 4 days and another every 6 days coincide every 12 days.
- 43
Property: GCD of Products
For positive integers, GCD(ab, ac) = a GCD(b, c) if a, b, and c share no other common factors beyond a.
- 44
Property: LCM of Products
LCM(ab, ac) involves taking the highest powers, but for distinct primes, it simplifies based on shared factors.
- 45
Edge Case: GCD of 0 and a Number
The GCD of 0 and a positive integer a is a, since a divides 0 and itself.
- 46
Edge Case: LCM of 0 and a Number
The LCM of 0 and a positive integer is 0, as 0 is a multiple of every integer.
- 47
How GCD Relates to Divisibility
GCD indicates the strongest common divisibility between numbers, helping determine if one divides another evenly.
- 48
How LCM Relates to Multiples
LCM is the smallest number that both original numbers divide into evenly, useful for finding common cycles.
- 49
Quick Calculation Trick for GCD
For small numbers, quickly list factors; for larger ones, use the Euclidean algorithm to reduce calculations.
- 50
Quick Calculation Trick for LCM
Memorize that for coprime numbers, LCM is their product, and adjust for shared factors by dividing by GCD.
- 51
GCD in Number Theory Basics
GCD is a foundational concept in number theory, used in GMAT for problems involving factors and divisibility rules.
- 52
LCM in Arithmetic Sequences
LCM helps identify the common difference in sequences where terms are multiples of given numbers.
- 53
Common Error: LCM Formula Mistake
A frequent error is forgetting to divide by GCD in the LCM formula, resulting in a multiple that is not the least.
- 54
Verifying GCD and LCM
To verify, check if the GCD divides both numbers and if the LCM is a multiple of both without being smaller than necessary.
- 55
Mental Math for GCD of Small Numbers
For small numbers like 8 and 12, mentally note factors: 8 has 1,2,4,8; 12 has 1,2,3,4,6,12; so GCD is 4.
- 56
GCD of Identical Numbers
The GCD of a number and itself is the number, as it divides itself evenly.
- 57
LCM of Identical Numbers
The LCM of a number and itself is the number, as it is the smallest multiple of both.
- 58
Comparative: GCD vs. LCM
GCD focuses on shared factors while LCM focuses on the smallest shared multiple, and they are related through the formula a b = GCD(a, b) LCM(a, b).
- 59
Summary: Key GCD Concepts
Key GCD concepts include its definition, calculation methods, and applications in simplifying and problem-solving on the GMAT.
- 60
Summary: Key LCM Concepts
Key LCM concepts involve its definition, formulas, and use in real-world scenarios like scheduling and fractions on the GMAT.