Skip to main content.

Solution to puzzle 116 (A generalization)

Skip restatement of puzzle.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!.


We will use mathematical induction on n.

The base case is trivially true for n = 1.

Let a be a positive integer less than or equal to (n + 1)!.
By the division algorithm there exist integers q and r such that a = q(n + 1) + r, with 0 less than or equal to r < n + 1.

Then q less than or equal to n!, and so, by the inductive hypothesis, q can be represented as the sum of at most n distinct divisors of n!.
That is, q = d1 + d2 + ... + dk, with k less than or equal to n.
Hence a = d1(n + 1) + d2(n + 1) + ... + dk(n + 1) + r.
That is, the sum of k + 1 (i.e., at most n + 1) distinct divisors of (n + 1)!.

It follows by induction 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!.

Source: K. Sengupta

Back to top