📂Number Theory

Prime Factorization Theorem

Theorem ¹

A prime number $p$ that divides a natural number $n : = d_{1} d_{2} \cdots d_{r}$ into $p \mid n$ must divide at least one of $d_{1} , d_{2} , \cdots , d_{r}$.

Description

$p \mid n$ means that $n$ is a multiple of $p$, that is, $p$ divides $n$. At first glance, it might seem obvious, but it’s a property of prime numbers that definitely requires a proof. Let’s consider whether this theorem always holds true not only for prime numbers.

Proof

First, let’s assume that $n$ is the product of two natural numbers, which is $n = ab$, and that $p$ does not divide both $a$ and $b$.

Existence of Integer Solutions to Linear Equations in Two Variables: For two integers $a,p$, $ax + py = \gcd (a,p)$ always has an integer solution.

Since $p$ does not divide $a$, $a$ is not a multiple of $p$, and because $p$ is a prime, it results in $\gcd (a,p) = 1$. Therefore, there exists $(x,y)$ satisfying $$ax + py = 1$$ . Multiplying both sides by $b$ yields $$abx + pby = b$$ . Given that $ab = n$ is a multiple of $p$ and $pb$ essentially has $p$ multiplied, it’s clearly a multiple of $p$. Therefore, $b$ is a multiple of $p$, which contradicts the assumption, and $p$ must divide one of $a$ or $b$.

Returning to $n = d_{1} d_{2} \cdots d_{r}$, based on the above discussion, $p$ must divide one of $d_{1}$ or $(d_{2} \cdots d_{r})$.

Even if $d_{1}$ is not divided, applying the same discussion to $d_{2} \cdots d_{r}$ eventually leads to the conclusion that $p$ must divide one of $d_{1} , d_{2} , \cdots , d_{r}$.

■