Question

Сколько натуральных (с единицы) чисел n среди первых 5000 таковы, что (n - 1)! делится на n?
Я знаю, что ответ 4330, но как это доказать математически ​

Answer 1

Объяснение:

Если n - простое число, то (n-1)! на делится на n, так как все его простые множители, очевидно, меньше n.

Если n можно представить в виде произведения двух различных чисел, то эти числа точно не больше чем n-1 и, следовательно, будут участвовать в произведении, и (n-1)! будет делиться на n.

Если же составное число n нельзя представить в виде произведения двух различных чисел, то n - квадрат простого числа p. Тогда в произведении (n-1)! будет p-1 чисел, кратных p, и, если p больше двух, (n-1)! будет делиться на p^(p-1), то есть и на p²=n.

Простых чисел до 5000 всего 669 (проверял программой, не знаю где найти это число), из составных исключением является n=2² => 3!=6 не делится на 4. Также 0!=1 делится на 1. Из 5000 чисел не подходят 670, значит остальные 4330 подходят.