Skip to content
Tutorials Center
My learning

Topics

Lesson 10 of 37 · Divisibility and Primes

The Fundamental Theorem of Arithmetic

Prove that every integer above 1 factors uniquely into primes, then use factorization to compute divisors, divisor counts, sums, gcd and lcm in Python.

Every integer greater than 1 can be written as a product of primes, and that product is unique apart from the order of the factors. For example 360 = 2 · 2 · 2 · 3 · 3 · 5 = 2³ · 3² · 5, and no other multiset of primes multiplies to 360. This is the Fundamental Theorem of Arithmetic, and the name is earned: almost everything about integers can be read off from their prime factorizations.

This lesson proves the theorem using Euclid's lemma from the last lesson, then turns factorizations into practical tools for divisors, gcd and lcm.

Existence

Claim: every integer n ≥ 2 is a product of primes (a prime counts as a product of one prime).

Proof by strong induction. If n is prime, done. Otherwise n = a·b with 1 < a, b < n. By the induction hypothesis a and b are each products of primes, so n is too. ∎

Uniqueness

Claim: if p₁p₂···pₘ = q₁q₂···qₖ with all pᵢ, qⱼ prime, then m = k and the q's are a rearrangement of the p's.

Proof. Induct on m. The prime p₁ divides the right-hand product, so by Euclid's lemma (applied repeatedly) it divides some qⱼ. Since qⱼ is prime and p₁ > 1, p₁ = qⱼ. Cancel that common prime from both sides and apply the induction hypothesis to what remains. ∎

Uniqueness is not obvious: in other number systems it fails. In the set of numbers a + b√−5, the number 6 equals both 2 · 3 and (1 + √−5)(1 − √−5), and none of these factors can be broken down further. The ordinary integers are special because of Euclid's lemma.

Python Factor numbers into primes

Press Run (or Ctrl + Enter) to see the result here.

Program input · what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

Reading things off the factorization

Write n = p₁^a₁ · p₂^a₂ ··· pₖ^aₖ. A divisor of n picks an exponent between 0 and aᵢ for each prime, and no other primes. So:

  • Number of divisors: τ(n) = (a₁ + 1)(a₂ + 1)···(aₖ + 1). For 360 = 2³·3²·5 that is 4 · 3 · 2 = 24.
  • Sum of divisors: σ(n) = ∏ (1 + pᵢ + pᵢ² + ... + pᵢ^aᵢ). For 360 that is 15 · 13 · 6 = 1170.
  • Perfect squares: n is a perfect square exactly when every exponent is even, which also explains why squares have an odd number of divisors.
Python Divisor count and sum from exponents

Press Run (or Ctrl + Enter) to see the result here.

Program input · what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

Numbers with σ(n) = 2n are called perfect numbers; 6 and 28 are the first two. Euclid proved that if 2ᵖ − 1 is prime then 2ᵖ⁻¹(2ᵖ − 1) is perfect, and Euler later proved every even perfect number has that form.

gcd and lcm from exponents

Compare the exponents of each prime in two numbers. The gcd takes the minimum exponent for each prime, the lcm takes the maximum. For 360 = 2³·3²·5 and 600 = 2³·3·5²: gcd = 2³·3·5 = 120, lcm = 2³·3²·5² = 1800. Since min(a, b) + max(a, b) = a + b, this also proves gcd · lcm = a · b.

Python gcd and lcm via exponents

Press Run (or Ctrl + Enter) to see the result here.

Program input · what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

Factoring is hard, but gcd is easy. For large numbers the Euclidean algorithm gives the gcd instantly, while computing the exponents would require factoring. Use the exponent view for understanding and the Euclidean algorithm for computing.

Showing that a number is not a perfect square, or a power

Because exponents are unique, a lot becomes simple. √n is rational only if n is a perfect square: in a fraction a/b with a² = n·b², compare exponents of each prime. A prime p with an odd exponent in n would give an odd exponent on the left and an even one on the right, impossible. That generalizes the √2 proof to every non-square.

What a factorization tells you

Divisor count Multiply (exponent + 1).
Divisor sum Multiply geometric sums.
gcd Take the smaller exponents.
lcm Take the larger exponents.
1 / 2

Check your understanding

Quick check · 4 questions

of 4 answered You scored / 4 · perfect!

  1. 1. What is the prime factorization of 360?

    8 * 9 * 5 = 360, and every factor is prime in the form 2^3 * 3^2 * 5.
  2. 2. How many positive divisors does 2^4 * 3^2 have?

    (4 + 1)(2 + 1) = 15.
  3. 3. Which result is needed to prove uniqueness of prime factorization?

    It lets you match a prime on the left side with one on the right side and cancel it.
  4. 4. For a = 2^3 * 5 and b = 2 * 5^2, what is gcd(a, b)?

    Take the smaller exponent of each prime: 2^1 * 5^1 = 10.

Summary

  • Every integer n ≥ 2 is a product of primes in exactly one way, apart from order.
  • Existence follows by strong induction; uniqueness follows from Euclid's lemma.
  • From n = ∏ pᵢ^aᵢ you get τ(n) = ∏ (aᵢ + 1) and σ(n) = ∏ (pᵢ^(aᵢ+1) − 1)/(pᵢ − 1).
  • gcd uses minimum exponents and lcm uses maximum exponents.
  • A number is a perfect square exactly when all exponents are even.

Next: Distribution of Primes