Number of Factors of an Integer
Given an integer N, there is a simple way to find the total number of its factors. The main tool for the feat is the prime number decomposition theorem.
Every integer N is the product of powers of prime numbers:
N = pαqβ· ... · rγ.
Where, p, q, ..., r are prime, while α, β, ..., γ are positive integers. Such representation is unique up to the order of the prime factors.
If N is a power of a prime, N = pα, then it has α + 1 factors:
1, p, ..., pα-1, pα.
Every prime in the prime number decomposition of N makes a similar contribution. Such contributions are independent of each other; according to the Product Rule of counting the total number of combinations - each a factor of N - equals
(α + 1)(β + 1) ... (γ + 1)
This formula helps answer such simple questions as, for example,
- What is the smallest positive integer that has 10 factors?
- What is the smallest positive integer that has 9 factors?
- What is the smallest positive integer that has 48 factors?
- What is the smallest positive integer that has more than 100 factors?
To answer the first question observe that 10 = 2·5, meaning that the number in question has just two prime factors in its decomposition - one with the exponent of
To answer the second question by the same token, observe that 9 = 3×3, implying again that the prime factorization of the number at hand includes only two prime factors,
For the third problem, my original thinking was to proceed as before: 48 = 2431 = 16×3, from which it appears
(α + 1)(β + 1) ... (γ + 1)
where each α, β, ..., γ is 1 or, some are, say, 3. Making this choice we arrive at the answer to #3:
2 · 2 · 3 · 5 · 7 · 11 = 4620
that also has 48 factors but is much smaller than 21532 = 294912.
An indication that the problem is not as simple as it first appeared to be came on 17 November, 2014 when an anonymous visitor left a comment with
|Contact| |Front page| |Contents| |Arithmetic|
Copyright © 1996-2018 Alexander Bogomolny
72386662