Primes and unique factorisation

Different splits can end with the same four prime factors

Eighty-four counters can be arranged as 6 groups of 14 or as 4 groups of 21. Continue splitting those positive whole-number factors: 6 = 2 × 3, 14 = 2 × 7, 4 = 2 × 2 and 21 = 3 × 7. Both routes end with two 2s, one 3 and one 7.

A factor tree records these successive products. Every internal label equals the product of its two children. The leaves in our first tree are 2,3,2,7; multiplying them gives 84. Moving a factor to another branch changes its position, not its value or its multiplicity.

Prepare with integer multiplication, then name the domain

The published lessons Counting, zero and natural numbers and Multiplication and division supply the positive integers and exact whole-number products. Revisit Powers, roots and the real number line for exponents and square roots. Integers below zero are optional here; the published lesson Negative numbers and absolute value prepares the final sign convention.

Write a | b when b = ak for some integer k: a divides b. A positive divisor of a positive n is a positive integer d with n = de for a positive integer e. Thus 1 and n always divide n. A proper nontrivial positive divisor lies strictly between them.

On a first reading, finish the definitions, factor trees and trial-division examples, then return to the proof of uniqueness. The induction and greatest-common-divisor lessons develop useful methods further; we define the needed induction, division and integer-combination facts here rather than requiring those planned lessons.

A prime is greater than 1 and has exactly two positive divisors

A prime p is a positive integer greater than 1 whose only positive divisors are 1 and p. A composite n is a positive integer greater than 1 that is not prime; equivalently n = ab with positive integers a,b both greater than 1. For example, 7 is prime, while 9 = 3 × 3 and 84 = 6 × 14 are composite.

The number 1 has just one positive divisor, so it is neither prime nor composite. Zero and negative integers are outside these positive-integer definitions. Allowing factors 1 in a prime list would create meaningless extra entries, such as 2 = 1 × 2 = 1 × 1 × 2.

An integer unit is an integer with an integer multiplicative inverse. The only units are 1 and −1: a product of two integer absolute values equals 1 only when both absolute values are 1. For positive factorisation we use the unit 1, not an extra prime. For a negative integer, factor its positive magnitude and retain one sign factor −1. Zero has no prime-product factorisation because a product of nonzero primes and units is nonzero.

Every integer greater than 1 can be split into primes

Strong induction proves a statement for every integer n ≥ 2 by proving its first case and showing that a case n follows whenever all smaller cases from 2 to n−1 hold. It is valid because a nonempty set of positive integers has a least member: a least failed case would have only successful smaller cases and would be forced to succeed.

For existence, the first case 2 is already prime. Now let n > 2 and assume every integer m with 2 ≤ m < n has a prime factorisation. If n is prime, its one-factor list suffices. If n is composite, write n = ab with 2 ≤ a,b < n. Both smaller factors have prime lists by the assumption; concatenate those lists to factor n.

This proves existence for every n ≥ 2. It also explains why a factor tree stops: a nontrivial split replaces a positive label by strictly smaller positive labels. A finite example illustrates the construction; the induction argument, rather than inspection of many trees, proves the universal claim.

Two local integer tools prepare the uniqueness proof

Euclidean division says that for a nonnegative integer t and a positive integer d there are integers q,r with t = qd + r and 0 ≤ r < d. Choose q as the greatest nonnegative integer with qd ≤ t; this exists among the finite candidates 0 through t. The remainder r = t−qd is nonnegative, and r ≥ d would allow q+1, a contradiction. The remainder is unique: two remainders in this range cannot differ by a nonzero multiple of d.

An integer linear combination of positive p and a is up + va with integer coefficients u,v, which may be negative. For p = 5 and a = 12, the combination 5·5 − 2·12 equals 1. A number dividing both p and a divides every such combination: if p = dh and a = dj, then up + va = d(uh + vj).

A prime dividing a product must divide one factor

Euclid’s lemma states: if p is prime and p | ab for positive integers a,b, then p | a or p | b. If p | a, the conclusion is immediate. Assume instead that p does not divide a; we will construct integers u,v with up + va = 1.

Consider all positive combinations up + va. This set is nonempty because p = 1·p + 0·a belongs to it, so it has a least member d = up + va. Divide p by d: p = qd + r with 0 ≤ r < d. The remainder r = (1−qu)p − qva is another integer combination. If r were positive, it would contradict minimality of d; hence r = 0 and d | p.

Likewise divide a by d: a = td + s. Here s = −tup + (1−tv)a is an integer combination with 0 ≤ s < d, so s = 0 and d | a. As d is a positive divisor of the prime p, d is 1 or p. The alternative d = p would imply p | a, contrary to our assumption. Therefore d = 1, giving up + va = 1.

Multiply this equality by b: b = upb + vab. Both terms on the right are divisible by p, because p | ab. Their sum is divisible by p, so p | b. This completes the lemma without presuming the next lesson’s greatest-common-divisor results.

The prime condition cannot be dropped. Although 6 | (2·3), neither 6 | 2 nor 6 | 3. A composite divisor can distribute its different prime factors between the two factors of the product.

Match and cancel primes, retaining every repeated copy

Suppose n = p₁···pᵣ = q₁···qₛ are two products of positive primes. Applying Euclid’s lemma repeatedly to the right-hand product shows that p₁ divides at least one qⱼ. A positive prime divisor of the prime qⱼ must equal qⱼ, so p₁ = qⱼ.

Reorder the right-hand factors to put this equal prime first, then cancel that positive nonzero factor from both products. Repeat on the remaining factors. If one list ended before the other, the empty product on that side would be 1 while the remaining product of primes would be at least 2, which is impossible. Thus both lists end together and match prime for prime.

Existence and this matching proof give the fundamental theorem of arithmetic: every positive integer greater than 1 has a prime factorisation unique up to order. Uniqueness concerns the prime inventory, not a unique sequence of splits. A factor tree that stops at a composite leaf is unfinished.

Exponents count repeated primes; the unit has an empty inventory

Sort the prime list and collect repetitions. For 84, both trees give 2²·3·7: the exponent 2 records two copies of 2, and the unwritten exponents of 3 and 7 are 1. An absent prime has exponent 0; a prime with a positive exponent really occurs in the product.

For 1, the empty product is 1 and every prime exponent is 0. This extends the inventory convention to positive integers without calling 1 prime. For −84, the prime inventory of its magnitude is the same and the sign is retained separately as −1·2²·3·7.

The two adjacent tree routes illustrate the same multiset, a collection that retains repeated entries but ignores their positions. The preceding proof explains why every possible complete route must agree, including routes not drawn here.

A composite integer has a prime divisor no greater than its square root

If n = ab with a,b > 1, at least one factor is at most √n: if both were larger, ab would exceed n. Suppose a ≤ √n and choose a prime divisor p of a by the existence theorem. Writing a = pc gives n = p(cb), so p divides n and p ≤ a ≤ √n. Therefore an integer n ≥ 2 is prime exactly when no prime p with p² ≤ n divides it.

The boundary is inclusive. For 121, the primes 2,3,5,7 do not divide it, but 11² = 121 and 11 does. Stopping before the equality case would call this square prime incorrectly. For 83, test 2,3,5,7 because 7² ≤ 83 < 11²; their remainders are 1,2,3,6, so 83 is prime.

An exact remainder r = 0 establishes divisibility; a nonzero remainder refutes it for that candidate only. Testing a few small primes proves primality only when the complete required range has been covered. Testing every integer from 2 through ⌊√n⌋, the greatest integer not exceeding √n, also works, though composite candidates are unnecessary.

A finite sieve excludes multiples while preserving their prime

To find primes from 2 through a fixed bound N, start with every integer in that range unmarked. In increasing order, take the next unmarked p with p² ≤ N and mark its multiples p²,p(p+1),p(p+2),… through N as composite. Keep p itself unmarked. Skip a marked candidate because it is already known composite.

Why start at p²? A smaller nontrivial multiple kp with 2 ≤ k < p has a prime divisor of k smaller than p, so an earlier sieve step has already marked it. Every newly marked number is composite because it has factors p and k at least 2. The next unmarked p is prime: if it were composite, a smaller prime divisor would already have marked it.

Once all primes with p² ≤ N have been processed, every remaining number from 2 through N is prime. A remaining composite would have a prime divisor no greater than its own square root, hence no greater than √N, and that step would have marked it. In the grid through 49, the 7 step must mark 49; stopping after 5 is too early.

Before the final step, unmarked means still a candidate, not yet certified prime. The grid marks the excluded 1 separately and shows the actual multiples removed at each step. Its equal-size cells are labels for integers, not a measured numerical area.

A finite list misses a prime divisor of its product plus 1

Take any nonempty finite list of distinct primes p₁,…,pₖ. Let M = p₁···pₖ and N = M+1. Since N > 1, it has a prime divisor q. Every listed pᵢ divides M but cannot divide N: otherwise it would divide N−M = 1, impossible for a prime. Therefore q is absent from the list. No finite list can contain all primes.

The constructed N need not be prime. For the list 2,3,5,7,11,13, M = 30030 and N = 30031 = 59·509. Both factors are prime and neither occurs in the original list. The proof promises a new prime divisor, not that adding 1 always makes the whole product prime.

Product of the listed primes: 30030

The constructed number’s complete prime factor list: 59·509

For the empty list, use empty product M = 1 and N = 2, which also supplies a prime not on that list. This existence argument says nothing about a simple pattern for successive prime gaps or an efficient way to enumerate primes in numerical order.

Predict the evidence before revealing the calculation

Compare two complete trees of 84, the trial candidates for a prime and two squares, successive finite sieve steps, and product-plus-one lists. Before revealing, decide what the displayed evidence will establish. A surviving sieve candidate and a trial with missing candidates do not justify the same conclusion as a completed test.

All interactive values use exact bounded integer arithmetic. The finite tables exhaust each stated case; universal existence, uniqueness and infinitude still rest on the proofs above.

Worked examples

Try it yourself

1. Classify 1,2,15,0 and −11 under the stated prime/composite definitions.

   Show the answer and reasoning

   2 is prime and 15 is composite. 1 is neither. 0 and −11 are outside the positive-integer classification.

   The divisor condition also requires an integer greater than 1. Fifteen has factorisation 3·5; a negative sign does not turn −11 into a positive prime.

2. A tree for 60 ends with leaves 4,3,5. Is it a prime factorisation? Finish it.

   Show the answer and reasoning

   It is unfinished because 4 is composite. The completed inventory is 2,2,3,5, so 60 = 2²·3·5.

   The product of the first leaves is already 60, but prime factorisation requires every leaf to be prime, not merely a correct product.

3. Does 2·3·2·7 differ as a prime factorisation from 7·2·2·3? What does 2² mean here?

   Show the answer and reasoning

   The order differs but the prime inventory is identical. The exponent 2 counts two factors equal to 2.

   Unique up to order retains multiplicity. It does not permit discarding a repeated factor or replacing 2·2 by one copy of 2.

4. Give the prime-inventory conventions for 1 and −60. Can 0 be a product of primes and units?

   Show the answer and reasoning

   1 has the empty prime inventory. −60 = −1·2²·3·5. Zero has no such product factorisation.

   The empty product is 1; −1 records the sign and is a unit rather than a positive prime. Every factor in a prime/unit product is nonzero.

5. In the existence proof, why are both factors of a composite n = ab with a,b > 1 smaller than n?

   Show the answer and reasoning

   Since b ≥ 2, a ≤ n/2 < n; similarly b ≤ n/2 < n.

   Both factors lie within the strong induction assumption 2 ≤ m < n, so their prime lists are already available. The assumption does not simply presume the case n.

6. Does d | ab always imply d | a or d | b for an arbitrary positive divisor d? Use d = 6,a = 2,b = 3.

   Show the answer and reasoning

   No. 6 divides 2·3 = 6, but divides neither 2 nor 3.

   Euclid’s lemma requires d to be prime. The distinct prime factors 2 and 3 of 6 can occur in separate factors of the product.

7. Why does testing only primes strictly smaller than √49 fail to certify 49?

   Show the answer and reasoning

   The excluded boundary candidate is 7, and 49 = 7² is composite.

   The theorem guarantees a divisor p ≤ √n, including equality. Tests by 2,3,5 alone leave the square divisor unchecked.

8. Which prime candidates must be tested for 83, and what do remainders 1,2,3,6 show?

   Show the answer and reasoning

   Test 2,3,5,7. None divides 83, so 83 is prime.

   7² ≤ 83 < 11², so the list covers every prime with p² ≤ 83. A complete nonzero-remainder list, not merely a partial list, supplies the conclusion.

9. When the increasing sieve reaches p = 5, why start its new marks at 25 instead of crossing out 5 or starting at 10?

   Show the answer and reasoning

   Keep 5 prime. Its smaller nontrivial multiples 10,15,20 are already marked; 25 is the first possibly new one.

   For kp < p² with k ≥ 2, a prime divisor of k is smaller than p and its step has already marked kp. Crossing out p itself would remove a prime.

10. A finite list of primes gives M, and a prime q divides M+1. Why can q not be on the list? Must M+1 be prime?

    Show the answer and reasoning

    A listed q would divide both M and M+1, hence 1, which is impossible. M+1 need not be prime.

    The contradiction concerns divisibility of the difference. The example 30031 = 59·509 shows why the guaranteed new prime divisor must not be confused with primality of the whole constructed number.

What to carry forward

• Prime and composite are classifications of positive integers greater than 1; 1 is a unit, not a prime.
• Strong induction supplies a prime factorisation for every integer greater than 1.
• Euclid’s prime-divisor lemma enables matching and cancellation, proving uniqueness up to order.
• The invariant prime inventory retains repeated copies as exponents; the sign of a negative integer is separate.
• A primality trial must cover every prime with p² ≤ n, including the square boundary.
• The increasing finite sieve starts new marks at p² and keeps p itself; unfinished survivors are candidates.
• A finite-list product plus 1 has a prime divisor outside that list, even when the number is composite.