Divisibility and factorization · Definition

Fundamental theorem of arithmetic

elementary number theorydivisibility and factorization

Before you start you need to know

Prime factorization seems obvious, but proving that it is unique requires a key property of primes. This result connects the existence of factors with the uniqueness of the decomposition.

Definition

Every integer greater than 1 can be written uniquely as a product of primes, up to the order of the factors. It is the foundation of most of elementary number theory.

\[n = p_1^{a_1} p_2^{a_2} \cdots p_k^{a_k}\]

Existence follows by strong induction: if \(n\) is not prime, then \(n = ab\) with \(1 < a, b < n\), and each factor is factored in turn. Uniqueness uses Euclid's lemma: if a prime \(p\) divides a product \(ab\), then \(p\) divides \(a\) or \(b\). Two different factorizations of the same integer then lead to a contradiction.

Take \(n = 360 = 2^3 \cdot 3^2 \cdot 5\). Any other way of writing 360 as a product of primes just rearranges these same factors, for example \(360 = 5 \cdot 2 \cdot 3^2 \cdot 2^2\), and no different prime ever appears. This shows that the exponents completely determine the number.

A typical mistake is to think the theorem holds in any ring of integers, but in \(\mathbb{Z}[\sqrt{-5}]\) the number 6 has two essentially different prime factorizations: \(2 \cdot 3\) and \((1+\sqrt{-5})(1-\sqrt{-5})\). Uniqueness depends on the Euclid property of primes in \(\mathbb{Z}\), not only on their definition.

Think about it

Why does uniqueness of prime factorization depend on Euclid's property?

Because if a prime divides a product, it divides one of the factors, which rules out two different factorizations.

Exercises 10

  1. What is the prime factorization of \(12\)?
  2. Two factorizations of \(30\) are \(2 \cdot 3 \cdot 5\) and \(5 \cdot 3 \cdot 2\). What does the fundamental theorem of arithmetic say about them?
  3. Which integer has the prime factorization \(2^3 \cdot 5\)?
  4. How many distinct prime factors does \(42\) have?
  5. If a prime \(p\) divides the product \(a \cdot b\) of two integers, what necessarily follows?
  6. What is the prime factorization of \(360\)?
  7. If \(n = 2^a \cdot 3^b\) and \(n = 72\), what are \(a\) and \(b\)?
  8. What is the least common multiple of \(2^3 \cdot 5\) and \(2 \cdot 3^2\)?
  9. How many positive divisors does \(60 = 2^2 \cdot 3 \cdot 5\) have?
  10. Let \(n = 900\). How many positive divisors does \(n\) have?

References

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