next up previous contents
Next: Applications of prime factorisation Up: Prime Numbers Previous: Prime Numbers   Contents

Uniqueness of prime factorisation

Lemma 6.5.4 (Gauss's Lemma)   Let $ p$ be a prime and let $ a,b$ be two natural numbers. If $ p \mid a b$, $ a,b \in \mathbb{N}$ then $ p \mid a$ or $ p \mid b$.

We mean ``inclusive or'' (v.s. definition def inclusive or in Chapter 2).

Proof. If $ p \nmid a$ then $ (p,a) = 1$ and so $ p \mid b$ by theorem (2.25). $ \qedsymbol$

For example, $ 7$ is a prime and it divides the number $ 1638=42 \cdot 39$. We see that $ 7 \mid 42$. This is enough. Conversely, as $ 7$ does not divide $ 38$ and does not divide $ 43$, $ 7$ does not divide $ 38 \cdot 43=$.

Theorem 6.5.5   Every natural number $ >1$ has a unique expression as the product of primes.

Proof. The existence part is Theorem 5.2. Now suppose $ n = p_1 p_2 \dots p_k = q_1 q_2 \dots q_l$ with the $ p_i$'s and $ q_j$'s primes. Then $ p_1 \mid q_1 \dots q_l$, so $ p_1 = q_j$ for some $ j$. By renumbering (if necessary) we can assume that $ j=1$. Now repeat with $ p_2 \dots p_k$ and $ q_2 \dots q_l$, which we know must be equal. $ \qedsymbol$

There are perfectly nice algebraic systems where the decomposition into primes is not unique, for instance $ \mathbb{Z}\left[\sqrt{-5}\,\right] = \{a + b \sqrt{-5} : a,b \in \mathbb{Z}\}$, where $ 6=(1 + \sqrt{-5}) (1-\sqrt{-5}) = 2 \times 3$ and $ 2,3$ and $ 1 \pm
\sqrt{-5}$ are each ``prime''. Or alternatively, $ 2 \mathbb{Z}= \{$   all even numbers$ \}$, where ``prime'' means ``not divisible by $ 4$''. These number systems are studied in Number Theory and in Abstract Algebra.
next up previous contents
Next: Applications of prime factorisation Up: Prime Numbers Previous: Prime Numbers   Contents
root 2002-06-10