Divisibility and factorization · Definition

Euclid's lemma

elementary number theorydivisibility and factorization

Before you start you need to know

This result extends to products of several factors the idea that a prime cannot be split between two numbers without dividing one of them. It is proved using Bézout's identity.

Definition

If a prime \(p\) divides the product \(ab\), then \(p\) divides \(a\) or \(b\). It is the key property that distinguishes primes from composite numbers.

\[p \mid ab \Rightarrow p \mid a \ \lor\ p \mid b\]

If \(p\) is prime and \(p \nmid a\), then \(\gcd(p,a)=1\). By Bézout's identity there are integers \(x,y\) with \(px+ay=1\). Multiplying by \(b\) gives \(pbx+aby=b\); since \(p \mid ab\), \(p\) divides \(aby\) and also \(pbx\), so \(p\) divides \(b\). By induction, the result holds for products of any number of factors.

Take \(p=5\), \(a=12\), \(b=15\). Since \(5 \mid 180\) with \(180=12\cdot 15\), and \(5\nmid 12\), it must be that \(5 \mid 15\), which is true. This checks the lemma in a concrete case before generalizing it.

A common mistake is applying the lemma to a composite number, for example claiming that \(6 \mid ab\) implies \(6 \mid a\) or \(6 \mid b\). With \(a=2\), \(b=3\) we have \(6 \mid 6\) but \(6 \nmid 2\) and \(6 \nmid 3\). The primality hypothesis is essential.

Think about it

Why must p be prime for the lemma to hold?

Because if p is composite it fails: \(6\) divides \(2\cdot 3\) without dividing \(2\) or \(3\).

Exercises 10

  1. If \(p\) is prime and \(p \mid ab\), what can you conclude?
  2. Does Euclid's lemma require \(p\) to be prime?
  3. Which is the correct statement of Euclid's lemma?
  4. If \(p\) is prime and \(p \mid 35\), which value can \(p\) take?
  5. Which statement about a prime \(p\) that does not divide \(a\) is true?
  6. If \(7 \mid 12x\), what can you conclude about \(x\)?
  7. If \(11 \mid ab\) and \(11 \nmid a\), what happens to \(b\)?
  8. If \(p\) is prime and \(p \mid a^2\), what follows?
  9. If \(p\) is prime and \(p \mid abc\) with \(p \nmid a\) and \(p \nmid b\), what follows?
  10. If \(p\) is prime, \(p \mid ab\), and \(p \mid a+b\), what follows?

References

  • David M. Burton, Elementary Number Theory, 7th edition, McGraw-Hill, 2011. cap. 2 y 3
  • Ivan Niven, Herbert S. Zuckerman, Hugh L. Montgomery, An Introduction to the Theory of Numbers, 5th edition, Wiley, 1991. cap. 1