Technique

Count ordered factorisations by handing out the primes

Arithmetic • Number System • Factors and Divisors

Statement

Let

n = p_{1} p_{2} \dots p_{k}

be a product of

k

distinct primes, each appearing to the first power. A prime to the first power cannot be split between two factors, so in any ordered tuple

(a_{1}, \dots, a_{m})

of positive integers with

a_{1} a_{2} \dots a_{m} = n

each

p_{i}

goes whole to exactly one of the

m

places; the

k

choices are independent and different choices give different tuples, so the number of such tuples is

m^{k}

How to use it

1Factorise $n$ first and check that no prime is repeated - that check is what licenses the count.
2Read $m$ off the question: ordered pairs give $2^{k}$ , ordered triples $3^{k}$ .
3The places are labelled, so $(1, 5, 6)$ and $(5, 1, 6)$ both count; if the question wants unordered factorisations, this count is too big and the repeats must be divided out by hand.
4As a cross-check, group on one factor instead: for each divisor $d$ of $n$ , count the tuples of the remaining $m - 1$ places with product $n / d$ , and add.

Worked example

In how many ordered pairs

(a, b)

of positive integers is

ab = 105

Step-by-step

1
$105 = 3 \times 5 \times 7$
Why: Three distinct primes, each to the first power, so the count applies.
2
Each of $3$ , $5$ , $7$ goes whole to $a$ or to $b$ : $2$ choices each
Why: A prime to the first power cannot be shared between $a$ and $b$ .
3
$2^{3} = 8$

Answer

8

Watch out

The count

m^{k}

needs every exponent to be

1

. With a repeated prime the exponent can be split, and the answer is larger:

ab = 12 = 2^{2} \times 3

has

6

ordered pairs, not

2^{2} = 4

. It also counts ordered tuples, and counts a place holding

1

as a legitimate factor.

Builds on

Prime factorisation

Also known as

number of ordered pairs with a given product, count ordered triples with product n, distribute prime factors among factors, ordered factorisations, number of ways to write n as a product of m factors

Count ordered factorisations by handing out the primes

Statement

Worked example

Appears in past papers

2020 (II)