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.

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

Professionals (100% free) Membership Required

You must be a Professionals (100% free) member to access this content.

Join Now

Already a member? Log in here
Related to: fundamental theorem of arithmetic, prime factorization, unique factorization, number theory, integer, prime number, Euclid, Gauss, canonical representation, multiplicative structure.

Leave a Reply

Your email address will not be published. Required fields are marked *

AVAILABLE FOR NEW CHALLENGES
Mechanical Engineer, Project, Process Engineering or R&D Manager
Effective product development

Available for a new challenge on short notice.
Contact me on LinkedIn
Plastic metal electronics integration, Design-to-cost, GMP, Ergonomics, Medium to high-volume devices & consumables, Lean Manufacturing, Regulated industries, CE & FDA, CAD, Solidworks, Lean Sigma Black Belt, medical ISO 13485

We are looking for a new sponsor

 

Your company or institution is into technique, science or research ?
> send us a message <

Receive all new articles
Free, no spam, email not distributed nor resold

or you can get your full membership -for free- to access all restricted content >here<

Historical Context

(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

Scroll to Top

You May Also Like