Fundamental Theorem of Arithmetic

From ProofWiki
Jump to navigation Jump to search


Theorem

For every integer $n$ such that $n > 1$, $n$ can be expressed as the product of one or more primes, uniquely up to the order in which they appear.


Proof

In Integer is Expressible as Product of Primes it is proved that every integer $n$ such that $n > 1$, $n$ can be expressed as the product of one or more primes.

In Prime Decomposition of Integer is Unique, it is proved that this prime decomposition is unique up to the order of the factors.

$\blacksquare$


Examples

Example: $18$

$18$ can be expressed uniquely as:

$18 = 2 \times 3 \times 3$


Example: $37$

$37$ is already prime, and so its prime decomposition is trivial

$37 = 37$


Example: $91$

$91$ can be expressed uniquely as:

$91 = 7 \times 13$


Also known as

The fundamental theorem of arithmetic is also known as the unique factorization theorem.

However, this is also sometimes used for the name of the equivalent result for the general Euclidean domain and it can be argued that the names are best kept separate.


Historical Note

The Fundamental Theorem of Arithmetic was known to Euclid.

However, it was first proved formally by Carl Friedrich Gauss in his Disquisitiones Arithmeticae in $\text {1801}$.


Sources

Retrieved from "https://proofwiki.org/w/index.php?title=Fundamental_Theorem_of_Arithmetic&oldid=735132"