Product Design, Manufacturing & Innovation Resources
Home » Fundamental Theorem of Arithmetic

Fundamental Theorem of Arithmetic

1801
  • Carl Friedrich Gauss
Study room with books and chalkboard illustrating the Fundamental Theorem of Arithmetic in number theory.

(generated image for illustration only)

This theorem states that every integer greater than 1 is either a prime number or can be uniquely represented as a product of prime numbers, disregarding the order of the factors. For example, \(1200 = 2^4 \times 3^1 \times 5^2\). This unique factorization is a cornerstone of number theory, providing a fundamental multiplicative structure for the integers.

The Fundamental Theorem of Arithmetic, also called the unique factorization theorem, consists of two main assertions for any integer \(n > 1\): first, that \(n\) can be written as a product of prime numbers (the existence part), and second, that this product is unique, apart from the order of the factors (the uniqueness part). The existence of a prime factorization is typically proven using strong induction. The base case is that 2 is prime. For the inductive step, assume every integer up to \(k\) has a prime factorization. For \(k+1\), it is either prime (and we are done) or composite. If it is composite, it can be written as a product of two smaller integers, \(a \times b\). By the induction hypothesis, both \(a\) and \(b\) have prime factorizations, and their product gives a prime factorization for \(k+1\).

The uniqueness part is more subtle and relies critically on Euclid’s Lemma, which states that if a prime \(p\) divides a product \(ab\), then \(p\) must divide either \(a\) or \(b\). To prove uniqueness, assume an integer \(n\) has two different prime factorizations: \(n = p_1 p_2 cdots p_k = q_1 q_2 cdots q_m\). The prime \(p_1\) divides the left side, so it must divide the right side. By Euclid’s Lemma, \(p_1\) must divide one of the \(q_j\). Since all \(q_j\) are prime, \(p_1\) must be equal to some \(q_j\). We can then cancel these terms from both sides and repeat the process, eventually showing that the two factorizations must be identical. While elements of this theorem appeared in Euclid’s *Elements* (c. 300 BC), Carl Friedrich Gauss provided the first clear statement and rigorous proof in his 1801 work *Disquisitiones Arithmeticae*, solidifying its foundational role in number theory.

UNESCO Nomenclature: 1101
– Pure mathematics

Type

Abstract System

Disruption

Foundational

Usage

Widespread Use

Precursors

  • Euclid’s proof of the infinitude of primes
  • Euclid’s Lemma
  • The concept of prime numbers and divisibility from ancient Greek mathematics
  • Development of mathematical induction as a proof technique

Applications

  • cryptography (e.g., RSA algorithm)
  • algorithms for finding the greatest common divisor (GCD)
  • solving diophantine equations
  • development of abstract algebra
  • computer science algorithms for integer factorization

Patents:

NA

Potential Innovations Ideas

Due to scrapping bot traffic, currently more than 40k per day, this content is reserved to community members.
> Login < or > Register < (100% free) to access this, so as all other restricted content and tools.

Related to: fundamental theorem of arithmetic, prime factorization, unique factorization, number theory, integer, prime number, Euclid, Gauss, canonical representation, multiplicative structure.

Historical Context

Fundamental Theorem of Arithmetic

1585
1779
1799
1801
1850
1875
1897
-550
1750
1790
1800
1844
1874
1893
1900

(if date is unknown or not relevant, e.g. "fluid mechanics", a rounded estimation of its notable emergence is provided)

Related Invention, Innovation & Technical Principles

Full size images and downloads are only available, 100% free, for registered members.

> Login <