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