CS2050 L15 GCD, Bezouts, Extended Euclidean, LCM
Overview
Abrahim Ladha develops greatest common divisors from Euclid’s algorithm through Bézout’s identity, showing both why the methods work and how the extended Euclidean algorithm finds coefficients. He uses Bézout’s identity to prove Euclid’s lemma and unique prime factorization, then derives prime-power rules for GCD and LCM and proves that GCD(A,B) × LCM(A,B) = A × B.
Key takeaways
- Euclid’s algorithm computes gcd(A, B) by repeatedly replacing the pair with (B, A mod B), preserving the GCD until the remainder reaches zero.
- Bézout’s identity guarantees integers S and T with AS + BT = gcd(A, B); for 25 and 11, back-substitution gives 25(−7) + 11(16) = 1.
- If gcd(A, B) = 1 and A divides BC, Bézout’s identity proves A divides C, a result known as Euclid’s lemma.
- Unique prime factorization follows because a prime dividing a product must divide one of its factors; matching prime factors across two factorizations eliminates any difference.
- With prime-power factorizations, the GCD uses minimum exponents and the LCM uses maximum exponents for each prime.
- The identity gcd(A, B) × lcm(A, B) = AB gives lcm(A, B) = AB / gcd(A, B), allowing LCM computation through Euclid’s efficient GCD algorithm.
Chapters
- A GCD D divides both inputs and is divisible by every other common divisor.
- The GCD is at least 1 for nonzero natural-number inputs; gcd(15, 35) = 5.
- Consecutive integers have GCD 1, and numbers with GCD 1 are called relatively prime or coprime.
- For prime P and 0 < A < P, gcd(A, P) must be 1.
- The recursive rule is gcd(A, B) = gcd(B, A mod B), with gcd(A, 0) = A.
- For gcd(25, 11), the remainders are 3, 2, 1, then 0, so the GCD is 1.
- Each step replaces the larger value with a smaller remainder until one input becomes zero.
- The correctness proof reduces gcd(A, B) = gcd(B, A − B) to showing each GCD divides the other.
- If D divides A and B, then it divides A − B, so it is a common divisor of B and A − B.
- Conversely, a common divisor of B and A − B also divides their sum A.
- Repeated subtraction yields the same remainder as A mod B, explaining why Euclid’s remainder steps preserve the answer.
- For nonzero natural numbers A and B, there are integers S and T such that AS + BT = gcd(A, B).
- The GCD is the least positive integer obtainable as an integer linear combination of A and B.
- For 3 and 6, combinations such as 3·1 + 6·0 produce the least positive value, 3.
- Every integer linear combination of A and B is a multiple of their GCD.
- Consider the positive values AS + BT and choose the least one, D, using the well-ordering principle.
- Divide A by D; the remainder is also an integer linear combination of A and B.
- A positive remainder smaller than D would contradict D’s minimality, so the remainder is zero and D divides A.
- The same argument shows D divides B; any common divisor of A and B also divides D, establishing D = gcd(A, B).
- For 25 and 11, Euclidean division gives 25 = 2·11 + 3, 11 = 3·3 + 2, and 3 = 1·2 + 1.
- Back-substitution rewrites the final nonzero remainder as a combination: 1 = 25·(−7) + 11·16.
- The coefficients S = −7 and T = 16 are checked by −175 + 176 = 1.
- Bézout coefficients are not unique; for example, 25·4 + 11·(−9) = 1 also works.
- Euclid’s lemma states that if A divides BC and gcd(A, B) = 1, then A divides C.
- Bézout gives integers S and T with AS + BT = 1; multiplying by C yields C = CAS + CBT.
- Since A divides BC, both terms on the right are divisible by A, so A divides C.
- The result formalizes why a factor coprime to B must divide the other factor C when it divides BC.
- Every integer n ≥ 2 can be expressed as a product of primes, as established earlier by strong induction.
- For example, 60 = 2²·3·5; prime factors act as the multiplicative building blocks of integers.
- The fundamental theorem of arithmetic adds uniqueness to existence, with prime powers encoding each number.
- Assume n has two different prime-product representations, p₁···pₖ and q₁···qₗ.
- A prime pᵢ on one side must divide the product of the q-primes on the other side.
- Repeated application of Euclid’s lemma forces pᵢ to divide some qⱼ; since both are prime, pᵢ = qⱼ.
- That contradicts the assumed unmatched prime, proving the prime factors and their multiplicities are unique up to order.
- Given prime-power factorizations, gcd(A, B) uses the minimum exponent for each prime.
- For 2²·5² and 3⁷·5, the only shared prime power is 5¹, so the GCD is 5.
- The GCD resembles an intersection of prime-factor content, while the later LCM rule resembles a union.
- Euclid’s algorithm computes GCDs efficiently, but finding a number’s prime factorization is described as difficult.
- An LCM is a number divisible by both inputs and least among their common multiples.
- Listing multiples gives 15, 30, 45, 60, 75, 90, 105 and 35, 70, 105, so lcm(15, 35) = 105.
- The direct listing method illustrates the definition but motivates a faster calculation.
- For each prime in A and B, the LCM uses the maximum of the two exponents; for powers of 2, lcm(2⁷, 2⁹) = 2⁹.
- The GCD uses minimum exponents and the LCM uses maximum exponents, so their exponents add to the sum of A’s and B’s exponents.
- This gives gcd(A, B) × lcm(A, B) = A × B, and therefore lcm(A, B) = AB / gcd(A, B).
- The formula computes an LCM using Euclid’s algorithm without requiring prime factorization.
- Write A and B as products of prime powers; multiply the LCM’s maximum exponents by the GCD’s minimum exponents.
- For each prime, max(aᵢ, bᵢ) + min(aᵢ, bᵢ) = aᵢ + bᵢ.
- Combining exponents gives the product of A’s prime powers times the product of B’s, which equals AB.
- The proof shows how prime-factor content is divided between GCD and LCM, analogous to intersection and union.
Transcript excerpt
0:00 All right. Welcome to uh CS 2050. The topic of today is uh greatest common divisors. Also known as GCDs. Sorry, let me adjust the volume. Okay. So So, if you're given two numbers, say A and B, uh which are For now, let's just suppose they're natural uh they're natural numbers. It doesn't really matter when we cast this to the integer case. Both are not zero.
0:49 One is allowed to be zero, but not both. We define the GCD of A and B to be some number D such that D divides A, uh D divides B, and three, uh D is the greatest. In essence, it is the largest, right? So, um the GCD of two numbers is a common divisor that they have that is the greatest of all common divisors, right? Um this second part could be formalized as if some C divides A and C divides B, that must imply that C divides D, where D is bigger, right? Um what can you say is true for every
1:36 GCD? Like every GCD is at least what? Yeah. So, it's never not zero. The GCD D is always at least one. Why? Yeah, one divides into every number, so it's at least one. Um what is the GCD of uh uh say 15 and uh 35? Five. Uh, what about the GCD of uh n and n plus one? For any n? Will be two. Yeah, it's one. It's like one of those will be even, the other will be odd.
2:23 We'll be able to prove that today as well. Every two consecutive numbers, if two if the GCD of two numbers are uh one, if GCD of A and B is one, we say A and B are relatively prime. Right? The term relatively prime means they
This is the start of the transcript. Save this video free for the whole transcript, searchable and time-coded.
In this course
Related notes
Summary, takeaways, and chapters were generated by AI from the video's transcript and may contain errors. The video belongs to its creator, Abrahim Ladha.