Разложение факториала на простые множители

Разложение факториала на простые множители

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

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

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

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

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

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

Предположим, что простых чисел конечное количество. Выпишем их все: p1, p2, … , pn.

Затем перемножим все эти числа и прибавим 1. Рассмотрим число N = p1 ∙ p2 ∙ … ∙ pn + 1.

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

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

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

Не нашли то, что искали? Воспользуйтесь поиском:

Лучшие изречения: Студент — человек, постоянно откладывающий неизбежность. 10808 — | 7380 — или читать все.

91.146.8.87 © studopedia.ru Не является автором материалов, которые размещены. Но предоставляет возможность бесплатного использования. Есть нарушение авторского права? Напишите нам | Обратная связь.

Отключите adBlock!
и обновите страницу (F5)

очень нужно

Название темы, для несведующих людей, может быть немного запутанным, и даже похже на тафтологическое выражение "масло масленное". На самом деле, под название темы подразумевается разложение факториала на простейшие множители с степенями.

Кто сталкивался с факториалами, знают что уже при значении 20, факториал достигает огромных значений 2432902008176640000

При факториале 100 значение получается еще больше, и возникает резонный вопрос а как можно представить факториал такого числа в более удобной и наглядной форме? Во первых это красиво, а во вторых полезно, так как отвечает еще и на попутно возникающий вопрос, например , сколько двоек/пятерок/семерок в факториале числа 2015?

Читайте также:  Записываем windows 7 на флешку

Что бы решить такую задачу, не надо вычислять факториал от числа 2015, а потом искать число целочисленных делений на тройку например , достаточно знать формулу по который рассчитывается число вхождений.

Итак если число p простое, то количество вхождений в факториал числа m, вычисляется как

где квадратные скобки означают что берётся целая часть от деления.

Самый простой пример, сколько раз входит число 3 в факториал 50?

то есть тройка встречается в числе 50! ровно 22 раза.

Теперь несложно, пробежавшись по всем простым числам от 1 до 50, для каждого из них узнать количество вхождений.

Окончательный ответ, в виде факторизации факториала пятидести будет иметь вид.

Решим еще один пример, часто встречающийся.

На какое количество нулей оканчивается факториал числа 306?

Для решения такой задачи надо знать что 10 это произвдение двух простых чисел 2 и 5.

Таким образом узнав количество вхождений пятерки в факториал ( количество вхождений двойки, естественно будет больше), мы узнаем какое количество нулей будет в факториала 306.

Ответ: на 75 нулей будет оканчиватся заданный факториал.

Что ты хочешь узнать?

Ответ

Проверено экспертом

Выведем общую формулу для разложения числа n! на простые множители. Запишем это разложение в виде , где — все простые числа не превосходящие n и — степени, с которыми они входят в это разложение, i=1. k. Докажем, что , где [. ] обозначает целую часть числа, т.е. для действительного числа х, запись [x] обозначает максимальное целое число не превосходящее х. Заметим, что в этой сумме всегда конечное число слагаемых, т.к. рано или поздно степень простого станет больше n, и с этого момента под целой частью будут числа меньшие 1, т.е. целая часть от них будет равна 0.

Читайте также:  Инструкция по эксплуатации микроволновки samsung

Доказательство. Пусть p — любое простое от 1 до n включительно. Понятно, что в разложении числа n! на простые множители будут встречаться только такие простые числа. Среди чисел 1, 2. n количество чисел делящихся на p равно [n/p]. Т.к. среди них есть числа делящиеся на p², p³. то количество чисел среди них, которые делятся на p только в первой степени равно [n/p]-[n/p²], т.е. мы из всех делящихся на р вычли все, делящиеся на р². Аналогично, количество чисел в ряду 1. n делящихся ровно на p² и не делящихся на p в степенях больших 2, равно [n/p²]-[n/p³]. Для степени p³ таких чисел будет [n/p³]-[n/p⁴] и т.д. Таким образом, количество чисел, у которых в разложении на простые p входит в разложение ровно в j-ой степени равно .

Значит в разложении n! на простые множители простое p входит в степени
([n/p]-[n/p²])+2([n/p²]-[n/p³])+3([n/p³]-[n/p⁴])+. =[n/p]+[n/p²]+[n/p³])+.
Как уже упоминал раньше, с некоторой степени все целые части будут равны 0, т.к. станет меньше 1 при больших j (а именно, при j>[ln(n)/ln(p)]).

Итак, чтобы разложить число 1980! нужно подставить n=1980 в эту формулу. Получаем, что 2 входит в разложение в степени
[1980/2]+[1980/2²]+[1980/2³]+. +[1980/2¹⁰]=
=990+495+247+123+61+30+15+7+3+1=1972. Т.к. 1980/2¹¹

Ссылка на основную публикацию
Adblock detector