# Solution to puzzle 116: Factorial divisors

Show that, for each n 3, n! can be represented as the sum of n distinct divisors of itself. (For example, 3! = 1 + 2 + 3.)

We will use mathematical induction on `n` to prove the slightly stronger result that, for each n 3, n! can be represented as the sum of n distinct divisors of itself, *with 1 as one of the divisors.*.

We have the base case, for n = 3: 3! = 1 + 2 + 3, with 1 as one of the divisors.

For the induction step, we assume the inductive hypothesis, that we have a representation for n = k, with 1 as one of the divisors.

That is, k! = 1 + d_{2} + d_{3} + ... + d_{k}, with 1 < d_{2} < ... < d_{k}.

Then (k + 1)! | = (k + 1) + (k + 1)d_{2} + ... + (k + 1)d_{k} |

| = 1 + k + (k + 1)d_{2} + ... + (k + 1)d_{k} |

That is, the sum of k + 1 distinct divisors of (k + 1)!, with 1 as one of the divisors.

It follows by induction that, for each n 3, n! can be represented as the sum of n distinct divisors of itself.

## A generalization

Show that any given positive integer less than or equal to n! can be represented as the sum of at most n distinct divisors of n!.

Hint - Solution

Source: Mathematical Miniatures, by Svetoslav Savchev and Titu Andreescu. See Chapter 15.

Back to top