What is prime factorization?

By Kardi Teknomo, PhD.

< Previous |Next | Content>

What make prime number interesting is because it’s unique prime factors. Prime factor (or prime factorization) of a positive integer number is the prime product of that number.

N = p₁ x p₂ x … x p_n, where p_i are prime numbers.

For example the prime factor of

27 = 3 x 3 x 3

100 = 2 x 2 x 5 x 5

12345 = 3 x 5 x 823

1234567 = 127 x 9721

123456789 = 3 x 3 x 3607 x 3803

Play around with the interactive program of Prime Factorization below. What are the prime factors of 12345678901234567890? What is the largest exponent? This interaction program determines the unique prime factors of an integer (canonical decomposition)

For simplest application of prime factor is to use it to ease division

For example

1260 = 2 x 2 x 3 x 3 x 5 x 7

36     = 2 x 2 x 3 x 3

Thus 1260 / 36 = 5 x 7 (after removing common prime factors)

Every integer has prime factorization. The nice property of prime factorization is its unique factors (after we sort the factors). This very nice property is also called fundamental theorem of arithmetic. Every positive integer can be written uniquely as a product of primes where the prime factors are written in ascending order of size. This unique format is also called canonical decomposition of a number.

For example:

24 can be written in many ways

24 = 1 x 24 = 2 x 12 = 3 x 8 = 4 x 6 = 2 x 2 x 6 = 2 x 3 x 4 and so on

However, if we use prime factor, there is only one prime factor that is

24 = 2 x 2 x 2 x 3

To obtain prime factors of a number larger than hundred, you may need to code it. In the next section, we will discuss algorithm to compute prime factorization

< Previous |Next | Content>

This tutorial is copyrighted.

Preferable reference for this tutorial is

Teknomo, Kardi (2010) Prime Factor Tutorial. http:\\people.revoledu.com\kardi\ tutorial\BasicMath\Prime\