# 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 ^{1}q^{4}.^{1}2^{4} = 48.

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, ^{2}3^{2} = 36.

For the third problem, my original thinking was to proceed as before: 48 = 2^{4}3^{1} = 16×3, from which it appears ^{15}3^{2}. Wayne Gabrielson in a comment below found an error in this thinking. Having 15 different factors does not obligate them all to be multiples of a single prime number, like 2^{15}. The exponent grows too fast. We may as well interpret 16 as the product

(α + 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 2^{15}3^{2} = 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 ^{3}3^{2}·5·7

|Contact| |Front page| |Contents| |Arithmetic|

Copyright © 1996-2018 Alexander Bogomolny

64969241 |