Докажите, что любое натуральное число, меньшее 2004!, можно представить в виде суммы не более чем 2004 делителей числа 2004!

Решение:

Докажем индукцией по n, что любое натуральное число, меньшее n!, представимо в виде суммы не более n делителей числа n!. При n = 2 утверждение верно. Пусть n > 2, a — данное число, r — остаток от деления a на n. Тогда a = nb + r, где b < (n — 1)!, и r < n. Тем самым либо r = 0, либо r является делителем n!. По предположению индукции число b представимо в виде суммы не более n — 1 делителей числа (n — 1)!, то есть b = d1 + d2 + … + dm, m < n. Тогда a = nd1 + nd2 + … + ndm + r.