# If a prime divides a product it divides one of the factors

**If a prime [math]\displaystyle{ p }[/math] divides a product [math]\displaystyle{ ab }[/math] it also divides either [math]\displaystyle{ a }[/math] or [math]\displaystyle{ b }[/math]**,
also called **Euclid's lemma**, is a classic result in number theory.

## Proof

Suppose [math]\displaystyle{ p }[/math] divides [math]\displaystyle{ ab }[/math] but doesn't divide [math]\displaystyle{ b }[/math]. Then [math]\displaystyle{ p }[/math] and [math]\displaystyle{ b }[/math] are co-prime, so their greatest common divisor is one. Bézout's lemma ensures that there are integers [math]\displaystyle{ x\text{, }y }[/math] such that [math]\displaystyle{ px + by = 1 }[/math]. Multiplying both sides with [math]\displaystyle{ a }[/math] we get [math]\displaystyle{ apx+aby=a }[/math]. Since [math]\displaystyle{ p }[/math] divides [math]\displaystyle{ ab }[/math] there is an integer [math]\displaystyle{ z }[/math] such that [math]\displaystyle{ ab=pz }[/math].

So the equation becomes [math]\displaystyle{ pax+pzy=a \Rightarrow p\left(ax+zy\right)=a }[/math], showing that [math]\displaystyle{ p }[/math] divides [math]\displaystyle{ a }[/math] which proves the assertion.

Statement of the claim | If a prime divides a product it divides one of the factors |

Level of certainty | Proven |

Nature | Theoretical |

Counterclaim | |

Dependent on | |

Dependency of |