Technique

Highest power of a number dividing a product

Arithmetic • Number System • Factors and Divisors

Statement

Write

N

in primes, and write the divisor as

d = p_{1}^{a_{1}} p_{2}^{a_{2}} \dots p_{k}^{a_{k}}

. If the prime

p_{i}

occurs

e_{i}

times in

N

, then

d^{n}

divides

N

exactly when

n a_{i} \leq e_{i}

for every

i

, so the largest such

n

is the SMALLEST of the quotients

⌊ \frac{e _{i}}{a _{i}} ⌋

: the prime that runs out first fixes the answer.

How to use it

1Factorise every base in the product into primes and carry each index through before collecting like primes.
2For $d = 10$ only the twos and the fives matter and each has $a_{i} = 1$ , so the answer is the smaller of those two counts — never their sum.
3When $d$ carries a repeated prime, such as $d = 12 = 2^{2} \times 3$ , divide that prime's count by its index before comparing.

Worked example

What is the largest

n

for which

1 2^{n}

divides

2^{10} \times 3^{4}

Step-by-step

1
$12 = 2^{2} \times 3$ , so $1 2^{n} = 2^{2 n} \times 3^{n}$
Why: Factorise the divisor and carry the index $n$ through to each prime.
2
Twos: $2 n \leq 10 \Rightarrow n \leq 5$ . Threes: $n \leq 4$
Why: Each prime imposes its own ceiling on $n$ .
3
$n = min (5, 4) = 4$

Answer

4

Watch out

Adding the two counts, or taking the larger instead of the smaller, is the usual slip: for

1 0^{n}

dividing

2^{23} \times 5^{20}

the answer is

20

, not

43

and not

23

. A repeated prime in

d

must also be divided out — the count of twos is not itself the ceiling when

d

4

12

Builds on

Prime factorisation Power of a power, and the move to a common base

Also known as

largest power of 10 dividing a product, trailing zeros of a product, highest power of a composite dividing a number, minimum of prime exponents, number of zeros at the end of a product