Competition problem — Number theory

Library / /351 of 520

Number theory Difficulty 6.3 National olympiad Prove it

2. The Fundamental Theorem of Arithmetic states that every positive integer greater than 1 can be decomposed into a product of a finite number of prime numbers. If the order of the prime factors in the product is not considered, then the decomposition is unique, i.e., $n = p_{1}^{a_{1}} \cdot p_{2}^{a_{2}} \cdots \cdots \cdot p_{k}^{a_{k}}$ , where $p_{i}$ are prime numbers, $\alpha_{i}$ are positive integers, and $1 \leqslant i \leqslant k$ . Below, we will prove its uniqueness. Let $n > 1$ have two prime factorizations,
$n = p_{1} p_{2} \cdots p_{k} = q_{1} q_{2} \cdots q_{t}$

Solution

We need to prove that $k=l$ and the prime numbers $p_{1}, p_{2}, \cdots, p_{k}$ are a permutation of $q_{1}, q_{2}, \cdots, q_{l}$ .
From (1), we see that $p_{1}$ divides $q_{1} q_{2} \cdots q_{l}$ , so $p_{1}$ divides $q_{1}$ or $q_{2} \cdots q_{l}$ . If $p_{1} \mid q_{1}$ , since $p_{1}$ and $q_{1}$ are both primes, then $p_{1}=q_{1}$ ; if $p_{1} \mid q_{2} \cdots q_{l}$ , repeating this argument shows that $p_{1}$ must be the same as one of $q_{2}, \cdots, q_{l}$ . Therefore, we can cancel $p_{1}$ from both sides of (1), then consider $p_{2}$ , and repeat the process. Eventually, we find that the two prime factorizations of $n$ are identical. Proof completed.

Want a route through all this instead of an archive? The track puts 2,000 problems in a working order, from AMC 10 level to the IMO shortlist.

Source: NuminaMath-1.5, licensed Apache-2.0. Statement and solution reproduced as published; topic and difficulty added by this site.