Euclid’s lemma is a famous result in number theory which states that, if a prime divides a product of integers, then the prime has to divide at least one of those integers. In this video, we prove a generalization of this fact called Gauss’s divisibility lemma, and deduce Euclid’s lemma from it. The proof of the former will rely on Bézout’s lemma from divisibility theory.