Math 2.0

Number theory Divisibility and primes Theorem

Fundamental theorem of arithmetic

Builds on Prime factorizationExistence of prime factorizationEuclid's lemma

Statement

Each positive integer nn has exactly one prime factorization. That is, there are primes p1≤p2≤⋯≤pkp_1 \le p_2 \le \dots \le p_k with n=p1p2⋯pkn = p_1 p_2 \cdots p_k. If also n=q1q2⋯qln = q_1 q_2 \cdots q_l with primes q1≤q2≤⋯≤qlq_1 \le q_2 \le \dots \le q_l, then k=lk = l and pi=qip_i = q_i for each ii.

Remarks

The existence of prime factorization gives the first part. The uniqueness follows from Euclid's lemma. The statement uses the convention that 11 is not prime. If 11 were prime, 6=2⋅3=1⋅2⋅36 = 2 \cdot 3 = 1 \cdot 2 \cdot 3 would have two factorizations. Unique factorization fails in some rings. In ℤ[−5]\mathbb{Z}[\sqrt{-5}], 6=2⋅3=(1+−5)(1−−5)6 = 2 \cdot 3 = (1 + \sqrt{-5})(1 - \sqrt{-5}) gives two different factorizations into irreducible elements.

History

Euclid's Elements contains the main steps of the proof, in Book VII, Propositions 30 to 32, and in Book IX, Proposition 14. Gauss proved the uniqueness in his Disquisitiones Arithmeticae of 1801.

Reading path

To understand this page from the ground up, read these 7 pages in order. The foundations come first.

Show the path as a graph
Divisibility, definition, no evidence levelDivisibilitydefinitionPrime number, definition, no evidence levelPrime numberdefinitionEuclid's lemma, statement, no evidence levelEuclid's lemmastatementExistence of a prime divisor, statement, no evidence levelExistence of a prime …statementPrime factorization, definition, no evidence levelPrime factorizationdefinitionExistence of prime factorization, statement, no evidence levelExistence of prime fa…statementFundamental theorem of arithmetic, statement, no evidence levelFundamental theorem o…statement
Each page uses the pages above it. The colour of the bar on a box shows how strong the evidence is, and the box also gives it as text. The list has the same pages.
  • no evidence level
  1. Divisibility definition
  2. Prime number definition
  3. Euclid's lemma statement
  4. Existence of a prime divisor statement
  5. Prime factorization definition
  6. Existence of prime factorization statement
  7. Fundamental theorem of arithmetic statement

Where this leads

6 pages build on this one.

Further reading

  1. Web https://en.wikipedia.org/wiki/Fundamental_theorem_of_arithmetic, lead section
About this page
Tag084HH1NDCB
URIm2://084HH1NDCB
Aliasesunique-factorization-theorem, unique-prime-factorization-theorem
Kindstatement, theorem
WritingW1 stated
MSC11A51
StatusThis copy of the site has no build data. Run m2 status 084HH1NDCB.
UsesPrime factorization, Existence of prime factorization, Euclid's lemma
Same as

Markdown · JSON · Edit on GitHub

What this page needs for W2

  • edge about out: the concepts that the statement is about (0 of 1)
  • edge proves in: at least one proof node (0 of 1)
  • edge instance_of or illustrates in: one example that shows the statement at work (0 of 1)
  • explanation L2 (0 of 1)

The writing levels say how complete the text of a page is. They do not measure its truth.

What links here

Used by