Hi, in this video, we will start with the question of whether the representation of integers as a product of primes is unique. And we are going to prove Euclid's Lemma, which will help us to answer this question. So first let's consider this example. One have a very large number and is represented as a product of two integers on the left and as a product of another two integers on the right. And these pairs of integers look like big prime numbers. So does it prove that there can be two completely different representations of the same integer as a product of primes? What do you think? Well, actually, if you try more and you try to factor those big integers, it turns out that those are not prime. And that all those four big integers can be further factored into products of numbers like 137 times 571 and 137 times 727 and so on. And you see that on both sides on the left and on the right, we have the factor 137. And actually, all these three digit factors are on both sides of the equation. And so, in the end, it turns out that we can actually represent our big numbers as products of four numbers, 137, 337, 571, and 727. And these four are, in the end, prime numbers. And actually, those initial two representations of n as products of two numbers are not variant factorization's and this final representation is prime factorization. And so, it doesn't prove that there can be two different representations of n product of primes. But it doesn't prove vice versa, it doesn't prove that it is always possible to represent n as a product of primes in a single way. And we're going to study this question further. To help us, we're going to recall the following lemma, called Euclid's Lemma, that if p is a prime number, and p divides product of integers ab, then p divides either a or b. Let's go quickly through this proof. Suppose that this prime number p doesn't divide a. Then consider the greatest common divisor of a and p. This greatest common divisor divides p, so either it is equal to 1 or it is equal to p, because p is prime. But we know that p doesn't divide a, so this greatest common divisor cannot be equal to p. And so, it necessarily is equal to 1. And in this case, we proved in the previous module that multiplication by a, module b is invertible, which means that there exist some integer x, such that x times a is equal to 1 module p. And then, if p divides the product of a and b, it means that product of a and b is equal to 0 module of p. Let's multiply both sides by x, and conclude that x times a times b is equal to 0 mod p. Then, notice that x times a is equal to 1, so we can just cancel these two terms, both x and a and gathered b is equal to 0 mod p. And if b is equal to 0 mod p, then p divides b. So we proved our theorem, proved that, if p doesn't divide a, then p divides b. And we're also going to prove a corollary, that if a prime number p divides product of several integers, then p divides at least one of these integers. Indeed if p divides some product of a1 x a2 x ak, we can represent this product of ak integers as a product of two integers a1 and the product of all other integers from a2 to ak. So by the previous lemma, by Euclid's Lemma, either p divides a 1, and we're already good, or p divides the product of all the other integers, a2 up to ak. Then we can again present this product as the product of a2 and a3 through ak. And in the latter case, p divides either a2 or product of a3 through ak. And again, if p divides a2, we're good. Otherwise, it divides either a3 or product of everything else, and so on. So, and then we get that p is going to divide at least one of these several integers. And we're going to use this fact to prove that prime factorization of any integer is unique up to order of prime factors. [MUSIC]