    Next: Applications of prime factorisation Up: Prime Numbers Previous: Prime Numbers   Contents

## Uniqueness of prime factorisation

Lemma 6.5.4 (Gauss's Lemma)   Let be a prime and let be two natural numbers. If , then or .

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

Proof. If then and so by theorem (2.25). For example, is a prime and it divides the number . We see that . This is enough. Conversely, as does not divide and does not divide , does not divide .

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

Proof. The existence part is Theorem 5.2. Now suppose with the 's and 's primes. Then , so for some . By renumbering (if necessary) we can assume that . Now repeat with and , which we know must be equal. There are perfectly nice algebraic systems where the decomposition into primes is not unique, for instance , where and and are each prime''. Or alternatively, all even numbers , where prime'' means not divisible by ''. These number systems are studied in Number Theory and in Abstract Algebra.    Next: Applications of prime factorisation Up: Prime Numbers Previous: Prime Numbers   Contents
root 2002-06-10