📂Number Theory

Fundamental Theorem of Arithmetic Proof

Theorem ¹

Every natural number $n >2$ has a unique prime factorization $n = p_{1} p_{2} \cdots p_{r}$. The order of the primes $p_{1} , p_{2} , \cdots , p_{r}$ is ignored.

Explanation

It may seem strange that a property we’ve naturally used since elementary school requires proof, but it is extremely important. The fact that this is so simple perhaps serves as evidence that it merits the name theorem.

Proof

Elementary Proof

Part 1. Existence

Given $2=2$ and $3= 3$, and $4 = 2^2$, there exists a unique prime factorization. For all possible $n$, let’s find the prime factorization, and say the last number is $N$. Here, $N+1$ could be a prime or a composite number, so let’s check both cases.

• Case 1. If $N+1$ is Prime
  If $N+1$ is a prime, then it is its own prime factorization.
• Case 2. If $N+1$ is Composite
  If $N+1$ is composite, it can be represented as the product of two natural numbers $N+1 = n_{1} n_{2}$.

Since we’ve found the prime factorization for all natural numbers up to $N$, $$ n_{1} = p_{1} p_{2} \cdots p_{m} \\ n_{2} = q_{m+1} q_{m+2} \cdots q_{r} $$, by simply multiplying, we obtain $N+1 = p_{1} p_{2} \cdots p_{r}$, thus we can determine the prime factorization of $N+1$. Since we can find the prime factorization for $N+1$ in both cases, all natural numbers greater than $2$ have a prime factorization.

---

Part 2. Uniqueness

Now we need to show that $n = p_{1} p_{2} \cdots p_{r}$ is unique.

Assuming that $n$ has a non-unique prime factorization, so that $n = p_{1} p_{2} \cdots p_{r} = q_{1} q_{2} \cdots q_{s}$ holds. The order does not affect uniqueness, so for convenience, let’s say $p_{1} \le p_{2} \le \cdots \le p_{r}$.

Prime Factorization Principle: If a prime $p$ divides a natural number $ n : = d_{1} d_{2} \cdots d_{r}$ such that $p \mid n$, then $p$ must divide at least one of $d_{1} , d_{2} , \cdots , d_{r}$.

Since a prime dividing some number must divide at least one of its factors, $p_{1}$ must divide one of $q_{1} , q_{2} , \cdots , q_{s}$. The order is free, so a divisible $q_{i}$ by $p_{1}$ can be considered as $q_{1}$, and $q_{1}$ could substitute for $q_{i}$.

However, since $q_{1}$ is also a prime like $p_{1}$, $p_{1} = q_{1}$ holds and $$ p_{1} p_{2} \cdots p_{r} = q_{1} q_{2} \cdots q_{s} $$, eliminating both from each side gives $$ p_{2} \cdots p_{r} = q_{2} \cdots q_{s} $$. The same method continues until one side becomes $1$. If the other side is not $1$, the product of primes must be greater than $1$, making the equation invalid. Therefore, $$ p_{1} =q_{1} \\ p_{2} = q_{2} \\ \vdots \\ p_{i} = q_{i} \\ \vdots $$ must hold, and finally, $p_{r} = q_{s}$ must be true.

■

Algebraic Proof

Algebraic Proof of the Fundamental Theorem of Arithmetic: The ring of integers $\mathbb{Z}$](../587) is a PID, thus a UFD.

■

Code

Below is the implementation of prime factorization in R. It’s fast because it doesn’t need to check for primes, using a list of primes instead. As an algorithm, it’s virtually useless. It returns the factorization in list form, which might be less readable. If you want it in exponential form, simply use the built-in function table() on the returned vector.

prime = read.table("../attachment
                   /cfile8.uf@25411C3C5968BBE322F0D4.txt"); prime = prime[,1]
 
factorize<-function(p)
{
  q=p
  factors<-numeric(0)
  i=1; j=1
  while(q!=1)
  {
    if(q%%prime[i]) {i=i+1}
    else
    {
      q<-q/prime[i]
      factors[j]<-prime[i]
      i=1
      j=j+1
    }
  }
  return(factors)
}
 
factorize(54)
factorize(101)
factorize(256)
factorize(420)
table(factorize(420))

Here is the result of running the code.