To do this , we use the following lemma : if a prime number p divides a product ab , then it divides a or it divides b ( Euclid 's lemma ) . The key step in proving uniqueness is Euclid 's proposition 30 of book 7 ( known as Euclid 's lemma ) , which states that , for any prime number p and any natural numbers a , b : if p divides ab then p divides a or p divides b.