Hi. In this video we're going to draw some useful implications of the unique factorization theorem that we proved in the previous video. First, is some simple divisibility criterion that we now have. So, when does m divide n if you know their prime factorization? And the answer is, if we consider canonical representations of both m and n, then m divides n when first, all prime factors of m are among prime factors of n, and if PI is equal to QJ, if prime factor of M corresponds to the J_th prime factor of N. Then it must be that the corresponding degree in which this prime factor goes into M is less than or equal to the degree in which this prime factor goes into the representation of N. So, we can just compare the sets of prime factors of both numbers and then we can compare the degrees of the corresponding prime factors. If this set of prime factors of M is a subset of the set of prime factors of N and the corresponding degrees for M are less than or equal to the degrees for N, then M divides N. Another question that we want to answer easily is, when numbers M and N are coprime. And integers M and N are called coprime is their Greatest Common Divisor is equals to 1. And given canonical representations, this again easier to say that M and N basically don't have any common divisors and in particular, they don't have any common prime factors and so Greatest Common Divisor of M and N is equals to 1 if and only if there are no common prime factors between prime factors of M and prime factors of N. So we just compare the sets of prime factors in the canonical representations and if those sets don't intersect then numbers M and N are coprime. Another question is how to compute the Greatest Common Divisor itself in case it maybe not equal to 1? So, that set of numbers P1, P2 and so on up to Pk be all the prime divisors of M and N both of them, not just one of these numbers, but the union of the sets of prime factors of both these numbers. Then we can represent both numbers M and N as product of these primes in some degree. Note that some of these degrees alpha I and beta I can be equal to zero. In this case but still it can represent them both as products of the same primes in some different degrees. And then what we need to take is in each column, we need to take this prime in some degree and this degree must be less than or equal to the corresponding degree in both M and N because this number must divide both M and N and we just learned the divisibility criterion, that the degree of the prime factor in the number that divides another number should be less than or equal to the corresponding degree in the number it divides. So, for the Greatest Common Divisor that divides both M and N, the degrees must be less than or equal to the degrees in both M and N but this is the greatest common divisor so this should be the greatest degrees which still satisfy this property. And these are the minimums of the corresponding Alpha I and beta I. So greatest common divisor of M and N is the product of P1 to the power of minimum of Alpha 1 and beta 1 times P2 to the degree of minimum of alpha 2 and beta 2 and so on. Because these minimums are less than the corresponding alpha I and beta I, and these are the greatest degrees possible which are less than both alpha I and beta I. So, now that computing greatest common divisor is actually algorithmically much easier than prime factorization. Computing greatest common divisor can be done with Euclid's algorithm that we learned in the previous model. And still no efficient algorithm is known for prime factorization. So, you shouldn't actually try to do prime factorization to compute GCD. It is just convenient to know how to compute GCD given prime factorization because it can lead to some other useful conclusions. But if you want to actually compute GCD, you should use Euclid's algorithm. It is fast and pretty simple. Another useful function of two numbers is called least common multiple. It is very similar to the greatest common divisor, but in some sense its vice versa. So, the least common multiple LCM of two integers A and B is the smallest positive integer X such that both A and B divide X. Now, let's consider some examples. The least common multiple of 1 and 10 is 10, because 10 divides 10 and 1, and of course, 10 is a common multiple of both 1 in 10. But any number less than 10 cannot be the LCM because 10 must divide it, and so it must be at least 10. And for 2 and 3, the smallest number such that both 2 and 3 divides it is 6 because 2 doesn't divide 3, 3 doesn't divide 4, 2 doesn't divide 5 and now 6 is the least common multiple because both 2 and 3 divide 6. And to other example is least common multiple of 2 and 4 is 4 because 2 divides 4. And in the case when A divides B, the least common multiple is just B. And the least common multiple of 4 and 6 is 12. So now how to compute LCM it in the general case, so let's again consider all the prime factors of both M and N, P1, P2 and up to PK. And then represent both M and N as products of these prime numbers in some degrees, some of which can be zero. Then the least common multiple must be a number that both M and N divide, and so it must contain all these prime factors. It doesn't need to contain any other prime factors because then it won't be the least common multiple. And now we need to determine which degrees of these prime factors do we need. So, these degrees must be greater or equal to the corresponding degrees in both M and N, so that both M and N divide this number. So, we can just take the maximums of alpha I and beta I and take PI in this corresponding degrees, and that will be the least common multiple. So, this formula is very similar. As you can notice to the formula for Greatest Common Divisor, we just replace minimum with maximum. Now, that for any alpha and beta, minimum of alpha and beta plus maximum of alpha and beta is just equal to the sum of alpha and beta. And so, if we multiply the corresponding factors in the GCD and LCM, P1 to the degree of minimum of alpha 1 beta 1 times P1 to the degree of maximum of 1 beta 1, we will get P1 to the sum of alpha 1 and beta 1. And this is important because if we now represent M and N as the product of these set of primes from P1 to Pk and we also represent GCD and LCM as products of these primes in the corresponding minimum and maximum degrees, then we'll notice that the product of MN is product of these PI in the degrees of alpha I plus beta I. And also the product of GCD and LCM will be equal to the same number because minimums and maximums when we sum them up is the same as if we summed up alpha I and beta I. And so, the product of GCD and LCM for two numbers is equal to their product. And this in turn gives us a way to quickly compute LCM because we already know that to compute GCD we can use Euclid's algorithm and now LCM can be represented as a MN divided by GCD. So, we can easily compute the products to numbers, and then we compute GCD and Euclid's algorithm. And then by dividing those two we can get the least common multiple. So, now, we have some useful conclusion from the prime factorization although we don't need prime factorization itself to compute either GCD or LCM. From this presentation, we concluded with a fast algorithm to compute LCM which we didn't know before. So another Lemma that we're going to use in the next lectures is that if A divides N and B divides N and A and B are coprime then there are product divides N. So to prove it, consider all prime factors of A and B so all prime factors of A are among prime factors of N and degrees of those factors in N are bigger or equal to the corresponding degrees in A. The same goes for B and also as GCD of A and B equal to 1, A and B don't share prime factors we learned that in the beginning of this video. So now we can say that all prime factors of both A and B are in N they don't intersect so all the prime factors of their product are also in N and the degrees in which they represent AB are also less than or equal to the degrees in which they represent N, so AB divides N necessary. And in conclusion, using the unique factorization theorem, we made an easy criterion for divisibility of two numbers given their prime factorizations. We characterized coprime numbers that they don't share prime factors. We can compute GCD and LCM using prime factorizations. However, prime factorization is a hard problem and Euclid algorithm is fast. So, actually, we need to use Euclid's algorithm to compute GCD and given that GCD times LCM is equal to the product of the numbers. We can also compute LCM from Euclid's algorithm and by computing MN and dividing by GCD. And we know now that if two coprime numbers divide some integer N then their product also divides integer N.
