Сколько натуральных (с единицы) чисел n среди первых 5000 таковы, что (n - 1)! делится на n?
Я знаю, что ответ 4330, но как это доказать математически
Ответы
Объяснение:
Если 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 подходят.
У четвёрки (4-1)! делится только на 2^(2-1)=2, то есть четвёрка не подходит.
А единица - не простое и не составное число, её лучше проверить отдельно: 0! = 1 - делится на 1.
Из 5000 чисел от 1 до 5000 вкл не подходят 669 простых + четвёрка, а остальные 4330 - подходят, для них (n-1)! делится на n.