chapter  2
16 Pages

Unique factorization

Something similar happens with the integers. In this case the role of atoms is played by the prime numbers, and every integer can be written as a product of primes. This decomposition is a crucial ingredient in the proof of many properties of the integers. However, it is not always easy to compute the decomposition of a given integer. If the number is large, factorization can be a very time-consuming process, making heavy demands of computer power.