Friday, September 26, 2025
HomeData Modelling & AIEuclid’s lemma

Euclid’s lemma

We are given two numbers x and y. We know that a number p divides their product. Can we say for sure that p also divides one of them?

The answer is no. For example, consider x = 15, y = 6 and p = 9. p divides the product 15*6, but doesn’t divide any of them.

What if p is prime?
Euclid’s lemma states that if a prime p divides the product of two numbers (x*y), it must divide at least one of those numbers.

For example x = 15, y = 6 and p = 5. p divides the product 15*6, it also divides 15.

The idea is simple, since p is prime, it cannot be factorized. So it must either be completely present in x or in y.

Generalization of Euclid’s lemma:
If p divides x*y and p is relatively prime to x, then p must divide y. In the above example, 5 is relatively prime to 6, therefore it must divide 15.

Reference:
https://en.wikipedia.org/wiki/Euclid’s_lemma

Please write comments if you find anything incorrect, or you want to share more information about the topic discussed above

Feeling lost in the world of random DSA topics, wasting time without progress? It’s time for a change! Join our DSA course, where we’ll guide you on an exciting journey to master DSA efficiently and on schedule.
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!

RELATED ARTICLES

Most Popular

Dominic
32320 POSTS0 COMMENTS
Milvus
84 POSTS0 COMMENTS
Nango Kala
6683 POSTS0 COMMENTS
Nicole Veronica
11854 POSTS0 COMMENTS
Nokonwaba Nkukhwana
11910 POSTS0 COMMENTS
Shaida Kate Naidoo
6795 POSTS0 COMMENTS
Ted Musemwa
7071 POSTS0 COMMENTS
Thapelo Manthata
6756 POSTS0 COMMENTS
Umr Jansen
6762 POSTS0 COMMENTS