📂Number Theory

Prime Decomposition Principle

Theorem ¹

For a prime $p$ and a natural number $ n : = d_{1} d_{2} \cdots d_{r}$, if $p \mid n$, then $p$ must divide at least one of $d_{1} , d_{2} , \cdots , d_{r}$.

Explanation

$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 is a property unique to primes that genuinely requires a proof. Let us consider whether the theorem above always holds even for non-primes.

Proof

First, let $n$ be the product of two natural numbers, that is, $n = ab$, and suppose that $p$ divides neither $a$ nor $b$.

Existence of Integer Solutions to a Linear Equation in Two Variables: For two integers $a,p$, the equation $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 prime, $\gcd (a,p) = 1$. Therefore there exists $(x,y)$ satisfying $$ ax + py = 1 $$ Multiplying both sides here by $b$ gives $$ abx + pby = b $$ By the premise, $ab = n$ is a multiple of $p$, and $pb$ obviously has $p$ multiplied into it, so it is a multiple of $p$ without any doubt. Therefore $b$ is a multiple of $p$, which contradicts the assumption, and so $p$ must divide one of $a$ and $b$.

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

Even if it does not divide $d_{1}$, applying the same argument again to $d_{2} \cdots d_{r}$ shows that in the end $p$ must divide one of $d_{1} , d_{2} , \cdots , d_{r}$.

■