Exercise 1123Number theory › PrimesL1Added 3 Nov 2026

Coprime products and primes

#coprime#product#prime

Statement

Let $p$ be prime and $a,b$ integers with $\gcd(a,p)=1$ . Show that if $p\mid ab$ , then $p\mid b$ .

Hint

Euclid's lemma with $p$ prime.

Show solutionHide solution

Euclid's lemma. If $p$ prime and $p\mid ab$ , then $p\mid a$ or $p\mid b$ .

Given $\gcd(a,p)=1$ . Since $p$ is prime, this means $p\nmid a$ . So $p\mid b$ .

Conclusion. This is the standard form of Euclid's lemma for primes.