Степень вхождения данного простого числа в разложение факториала

 

Несложно разложить на простые множители факториал натурального числа, воспользовавшись рассуждениями, наподобие только что приведённых для деления 100! на 5.

Каждое простое число p входит в разложение числа n! следующее количество раз:

(Обоснование формулы состоит в том, что сначала рассматривают числа, кратные p, затем кратные квадрату p, затем кратные кубу p, и так далее).

Количество слагаемых не бесконечно, поскольку начиная с некоторого места они равны нулю.

 

Теорема Евклида о бесконечности множества простых чисел

Доказательство бесконечности множества простых чисел.

 

Предположим, что простых чисел конечное количество. Выпишем их все: p₁, p₂, … , p_n.

Затем перемножим все эти числа и прибавим 1. Рассмотрим число N = p₁ ∙ p₂ ∙ … ∙ p_n + 1.

Это число не может быть простым, поскольку больше любого из простых чисел.

При этом оно не может быть и составным, поскольку не делится ни на одно из простых чисел.

Получаем противоречие, которое говорит о том, что простых чисел бесконечно много.