For really large numbers, say several millions of digits, there's an even faster method called the Half-GCD (HGCD) algorithm, where each step roughly halves the number of digits, hence it takes O(log log) steps. Each step still involves a constant number of basic arithmetic operations but is rather more complicated.
ab has the factors of a and of b, the gcd(a,b) is the product of their common factors, so ab will be a product of the factors not in common, multiplied by the factors they do share and all of those factors are appearing twice in the product, so if we devide ab by gcd(a,b) we still have one cope of both the shared and not shared factors of a and ab in ab/gcd(a,b)
algebraically: let a,b be positive integers. a and b can both be written as a unique factorization of primes. we know that (a,b) is the product of all the shared factors of a and b. call S the set of all of these factors and let d = (a,b) this means we can rewrite a as d * u1, where u1 is the product of all the factors of a not present in S. correspondingly, b can be written as d * u2 where u2 is the product of all the factors of a not present in S. then, ab can be written as (d * u1)(d * u2) = d^2 * u1 * u2. remember that the definition of least common multiple is the smallest integer divisible by both a and b. this means a | lcm(a,b) and b | lcm(a,b). since we want the lcm to be divisible by both a and b, the answer must contain (d * u1) and (d * u2). the simplest form of this is (d * u1 * u2) called m, where (d * u1) | m and (d * u2) | m. nothing can be simpler than this because any factors added would make it larger than m, and any factors removed would result in a missing factor from either d, u1, or u2 resulting in either (d * u1) | m or (d * u2) | m failing. to obtain (d * u1 * u2), we remember d = (a,b) and ab = d^2 * u1 * u2 to find (d * u1 * u2) = ab / d = ab / gcd(a,b). therefore, lcd(a,b) = ab / gcd(a,b).
For really large numbers, say several millions of digits, there's an even faster method called the Half-GCD (HGCD) algorithm, where each step roughly halves the number of digits, hence it takes O(log log) steps. Each step still involves a constant number of basic arithmetic operations but is rather more complicated.
ab has the factors of a and of b, the gcd(a,b) is the product of their common factors, so ab will be a product of the factors not in common, multiplied by the factors they do share and all of those factors are appearing twice in the product, so if we devide ab by gcd(a,b) we still have one cope of both the shared and not shared factors of a and ab in ab/gcd(a,b)
algebraically:
let a,b be positive integers.
a and b can both be written as a unique factorization of primes. we know that (a,b) is the product of all the shared factors of a and b. call S the set of all of these factors and let d = (a,b)
this means we can rewrite a as d * u1, where u1 is the product of all the factors of a not present in S. correspondingly, b can be written as d * u2 where u2 is the product of all the factors of a not present in S.
then, ab can be written as (d * u1)(d * u2) = d^2 * u1 * u2.
remember that the definition of least common multiple is the smallest integer divisible by both a and b. this means a | lcm(a,b) and b | lcm(a,b). since we want the lcm to be divisible by both a and b, the answer must contain (d * u1) and (d * u2).
the simplest form of this is (d * u1 * u2) called m, where (d * u1) | m and (d * u2) | m. nothing can be simpler than this because any factors added would make it larger than m, and any factors removed would result in a missing factor from either d, u1, or u2 resulting in either (d * u1) | m or (d * u2) | m failing.
to obtain (d * u1 * u2), we remember d = (a,b) and ab = d^2 * u1 * u2 to find (d * u1 * u2) = ab / d = ab / gcd(a,b).
therefore, lcd(a,b) = ab / gcd(a,b).
Really like the «better algorithm», seems so clean with respect to using it on computers.
I like it too, but I'm having trouble seeing how to use it to solve ax + by = (a,b)
At 8:42: "I'm not going to give an example of this, because this isn't really a course on algebra" 😂😂😂
Beside all the interesting and insping maths, I love your humor, which is legendedry: My rabbits are spherical. Made my day :D:D:D Thank you
Professor forgot to mention that these were *Diophantine* equations…
Thanks for this lectures
Thanks
Wgat about substracting twice? i mean, why not it preserves the factors that are common.
Lcm=ab/gcd(a,b) because ab has a factor of gcd(a,b)^2 :)
I think this only shows that lcm
Copy*, not cope
yeeeeeeeeeeeeeeeeeeeeeeeeee