# Fundamental Theorem of Arithmetic

The **fundamental theorem of arithmetic** (FTA), also called the *unique factorization theorem* or the *unique-prime-factorization theorem*, states that every integer greater than \(1\) either is prime itself or is the product of a unique combination of prime numbers.

#### Contents

## Definition

For every integer \(n\geq2\), it can be expressed as a product of prime numbers.

\[n=p_1^{\alpha_1}p_2^{\alpha_2}\dots p_i^{\alpha_i}. \ _\square\]

## Proof of the Existence of the FTA

The following proof shows that every integer greater than \(1\) is prime itself or is the product of prime numbers. It is adapted from Strong Induction wiki.

Base case: This is clearly true for \(n=2\).

Inductive step: Suppose the statement is true for \(n=2,3,4,\dots, k\).

If \((k+1)\) is prime, then we are done. Otherwise, \((k+1)\) has a smallest prime factor, which we denote by \(p\). Let \(k+1=p\times N\). Since \(N<k\), by our inductive hypothesis, \(N\) can be written as the product of prime numbers. That means \(k+1=p \times N\) can also be the written as a product of primes. We're done! \(_\square\)

## Proof of the Uniqueness of the FTA

The following proof shows that there is only one way to express an integer with the product of an unordered set of primes.

The proof uses **Euclid's lemma**: If a prime \(p\) divides the product of two positive integers \(a\) and \(b\), then \(p\) divides \(a\) or \(p\) divides \(b\) (or both).

Assume that integer \(n\) is the product of prime numbers in two different ways: \[\begin{aligned} n &= p_1p_2\dots p_i \\ &= q_1q_2\dots q_j. \end{aligned}\] For simplicity, we let the arrangements of prime be in ascending order.

By Euclid's lemma, since \(q_1, q_2, \dots, q_j\) are co-prime integers (in fact, they are all primes), \(p_1\) can and must divide only one of the primes. Note that \(q_1\) is the smallest prime, then we have \(p_1=q_1\). By the same method, we reach that all \(p_k=q_k\) and thus \(i=j\). Then we conclude that the combination of primes are the same. \(_\square\)

## The application of the FTA

Finding the number of divisors.

If \(n=p_1^{\alpha_1}p_2^{\alpha_2}\ldots p_i^{\alpha_i}\), then \(n\) has \(d(n)=(\alpha_1+1)(\alpha_2+1)\cdots (\alpha_i+1)\) divisors. \(_\square\)

Finding the greatest common divisor of integer \(a\) and \(b\).

If \[a=p_1^{\alpha_1}p_2^{\alpha_2}\ldots p_k^{\alpha_k},b=p_1^{\beta_1}p_2^{\beta_2}\ldots p_k^{\beta_k}\], then \[ \gcd(a,b) = p_1 ^{\min(\alpha_1, \beta_1)} p_2 ^{\min(\alpha_2, \beta_2)} \ldots p_k ^{\min(\alpha_k, \beta_k)}. \ _\square \]

Finding the lowest common multiple of integer \(a\) and \(b\).

If \[a=p_1^{\alpha_1}p_2^{\alpha_2}\ldots p_k^{\alpha_k},b=p_1^{\beta_1}p_2^{\beta_2}\ldots p_k^{\beta_k}\], then \[ \mbox{lcm}(a,b) = p_1 ^{\max(\alpha_1, \beta_1)} p_2 ^{\max(\alpha_2, \beta_2)} \ldots p_k ^{\max(\alpha_k, \beta_k)} . \ _\square\]

## Examples

Given the polynomial \[f(x)=x^n+a_1x^{n-1}+a_2x^{n-2}+\cdots + a_{n-1}x+a_n\] with integer coefficients \(a_1,a_2,a_3,\ldots, a_n\) and given that there exist four distinct integers \(a,b,c\) and \(d\) such that \[ f(a)=f(b)=f(c)=f(d)=5,\] show that there is no integer \(k\) for which \(f(k)=8\).

Let \(g(x)=f(x)-5\). Then we must have \[g(x)=k(x-a)(x-b)(x-c)(x-d)h(x)\] for some \(h(x) \in \mathbb{Z}[x]\). Let \(k\) be such that \(f(k)=8\), Then \(g(k)=3\) and we get \[4=k(x-a)(x-b)(x-c)(x-d)h(x).\] By the fundamental theorem of arithmetic, we can express 3 as a product of at most three different integers \((-1,-3,1)\). Since, \((x-a),(x-b),(x-c)\) and \((x-d)\) are all distinct, this is an obvious contradiction. \(_\square\)

**Cite as:**Fundamental Theorem of Arithmetic.

*Brilliant.org*. Retrieved from https://brilliant.org/wiki/fundamental-theorem-of-arithmetic/