Math Is Fun Forum

Daniel123

Member

Registered: 2007-05-23

Posts: 663

Distinct factors

I've just been doing some investigtion and I've found something quite nice.

The number of distinct factors a number has is given by the product of one more than the maximum power of each of the prime factors.

i.e. If

then the number of distinct factors n has is given by

.

This is relatively easy to prove. We have

. There is a total number of α_1 + 1 numbers that can be made from taking powers of p_1 from 0 to α_1, and similarly a total number of α_2 + 1 numbers that can be made from taking powers of p_2 from 0 to α_2. Each number from the first α_1 + 1 numbers can be paired with each of the α_2 + 1 numbers, giving a total of (α_1 + 1)(α_2 + 1) numbers. These can then be paired with the α_3 + 1 numbers that can be made from powers of p_3, giving a total of (α_1 + 1)(α_2 + 1)(α_3 + 1) numbers. This process can then be continued to give the desired result. 

For example, if n = 40 = 2^3 x 5^1, the number of distinct factors is (3+1)(1+1) = 8. This can be verified using the principals involved in the proof.

1       1
2       5
2^2
2^3

The possible factors of 40 are therefore: (1*1, 1*5), (2*1, 2*5), (2^2*1, 2^2*5), (2^3*1, 2^3*5), a total of 8.

Last edited by Daniel123 (2008-11-21 11:36:44)