GCD and LCM are two sides of the same coin. GCD finds the largest number that divides both; LCM finds the smallest number both divide into. Once you have prime factorizations, both become trivial: GCD takes the minimum exponent for each prime, LCM takes the maximum. And their product equals the product of the numbers.
The GCD of two integers a and b is the largest positive integer that divides both.
Notation: $ \gcd(a, b) $ or sometimes $ (a, b) $
Example: gcd(12, 18) = 6 because divisors of 12: {1,2,3,4,6,12}, divisors of 18: {1,2,3,6,9,18}, largest common = 6.
Coprime / relatively prime: gcd(a, b) = 1 means a and b share no common prime factors.
The LCM of two integers a and b is the smallest positive integer divisible by both.
Notation: $ \text{lcm}(a, b) $ or sometimes $ [a, b] $
Example: lcm(12, 18) = 36 because multiples of 12: {12, 24, 36, 48, ...}, multiples of 18: {18, 36, 54, ...}, smallest common = 36.
For any positive integers a and b:
\[ \gcd(a, b) \times \text{lcm}(a, b) = a \times b \]
This is incredibly useful: know one, you can find the other without recalculating.
\(Example: gcd(12,18) = 6, lcm(12,18) = 36, and 6 \\times 36 = 216 = 12 \\times 18.\) β
If you have prime factorizations, GCD and LCM are mechanical:
\(Example: 12 = 2^{2} \\times 3^{1}, 18 = 2^{1} \\times 3^{2}\)
This extends to three or more numbers the same way: GCD = min exponents, LCM = max exponents.
An efficient way to compute GCD without factoring:
\[ \gcd(a, b) = \gcd(b, a \bmod b) \]
Repeat until b = 0; then a is the GCD.
Example: gcd(48, 18):
This is much faster than factoring for large numbers.
If $ n = p_1^{a_1} p_2^{a_2} ... p_k^{a_k} $, the number of positive divisors is:
\[ \tau(n) = d(n) = (a_1 + 1)(a_2 + 1)...(a_k + 1) \]
Why: for each prime factor, you can choose exponent 0 through $a_i$ in a divisor. That's $a_i + 1$ choices per prime, multiply them.
\(Example: 12 = 2^{2} \\times 3^{1}, so d(12) = (2+1)(1+1) = 3 \\times 2 = 6 divisors. (1, 2, 3, 4, 6, 12)\) β
Sum of all positive divisors of n:
\[ \sigma(n) = \prod_{i=1}^{k} \frac{p_i^{a_i + 1} - 1}{p_i - 1} \]
Each factor is a geometric series: $1 + p_i + p_i^2 + ... + p_i^{a_i}$.
Example: Ο(12) = Ο\(((2^{2} \\times 3^{1}) = (1 + 2 + 4)(1 + 3) = 7 \\times\) 4 = 28. (1+2+3+4+6+12 = 28)\) β
A positive integer n is perfect if Ο(n) = 2n (sum of proper divisors = n itself).
Examples: 6 (1+2+3 = 6), 28 (1+2+4+7+14 = 28), 496, 8128...
Euclid-Euler theorem: Every even perfect number is of the form $ 2^{p-1}(2^p - 1) $ where $2^p - 1$ is a Mersenne prime. No odd perfect numbers are known.
Step 1: Prime factorizations.
\(24 = 2^{3} \\times 3^{1}\)
\(60 = 2^{2} \\times 3^{1} \\times 5^{1}\)
Step 2: GCD = min exponents.
gcd(24, 60) = \(2^{min(3,2)} \(\\times 3\)^{min(1,1)} \(\\times 5\)^{min(0,1)} \(= 2^{2} \\times 3^{1} \\times 5^{0} = 4 \\times\) 3 = 12\)
Step 3: LCM = max exponents.
lcm(24, 60) = \(2^{max(3,2)} \(\\times 3\)^{max(1,1)} \(\\times 5\)^{max(0,1)} \(= 2^{3} \\times 3^{1} \\times 5^{1} = 8 \\times 3 \\times\) 5 = 120\)
Step 4: Verify with product formula.
\(gcd \\times lcm = 12 \\times 120 = 1440\)
\(24 \\times 60 = 1440.\) β
Step 5: gcd + lcm = 12 + 120 = 132
Answer: 132
Step 1: Prime factorization of 180.
\(180 = 2^{2} \\times 3^{2} \\times 5^{1}\)
Step 2: Apply divisor-count formula: d(n) = \((a_{1}+1)(a_{2}+1)(a_{3}+1)...\)
\[ d(180) = (2+1)(2+1)(1+1) = 3 \times 3 \times 2 = 18 \]
Let's list them to verify:
From \(2^{0},^{1},^{2} and 3^{0},^{1},^{2} and 5^{0},^{1}\):
1, 2, 4, 3, 6, 12, 9, 18, 36, 5, 10, 20, 15, 30, 60, 45, 90, 180
That's 18 divisors. β
Answer: 18
Euclidean algorithm: gcd(a, b) = gcd(b, a mod b). Repeat until b = 0.
Step 1: gcd(126, 49)
126 Γ· \(49 = 2 with remainder 126 - 2 \\times 49 = 126 - 98 = 28\)
gcd(126, 49) = gcd(49, 28)
Step 2: gcd(49, 28)
49 Γ· 28 = 1 with remainder 21
= gcd(28, 21)
Step 3: gcd(28, 21)
28 Γ· 21 = 1 with remainder 7
= gcd(21, 7)
Step 4: gcd(21, 7)
21 Γ· 7 = 3 with remainder 0
= gcd(7, 0) = 7
Check: \(126 = 7 \\times 18, 49 = 7 \\times 7. gcd(18, 7) = 1.\) β
Answer: 7