next up previous
Next: Euler's phi function Up: Contents Previous: Prime numbers

Prime factorization

The factorization of 60 is the process of determining the primes whose product is 60. Clearly 6 is a divisor, and tex2html_wrap_inline116 . But 6 and 10 are not primes, so we must further factorize these numbers. Now 6 is the product of the primes 2 and 3, and 10 is the product of the primes 2 and 5. We have

eqnarray29

Multiplying these equations together, we get

displaymath118

Thus the prime factorization of 60 is 2, 2, 3, and 5. Note that 2 occurs twice in this list because it has to be multiplied in twice.

Let's try factorizing 60 in a different way. We observe that 60 is even, so 2 is a divisor. Dividing 60 by 2, we get 30. Now 30 is also even, so 2 is a divisor. Dividing by 2, we get 15. Finally, 15 is the product of 3 and 5. Thus the prime factorization is again 2, 2, 3, and 5.

A fundamental result in number theory is that the prime factorization of a positive number doesn't depend on how it is found, that there is one and only one prime factorization.



Lisa Eckstein
Mon Oct 21 22:46:13 EDT 1996