Математика · объяснение и практика

Как посчитать показатель простого числа в факториале

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

Синяя и оранжевая половины складываются в целый круг.

В теме Теория чисел: углубление · Учебная карта

В маршруте Новые структуры целой арифметики · 10 тем

Главная мысль

Показатель простого p в n! равен сумме целых частей n/p, n/p², n/p³ и далее. Каждая степень p учитывает ещё один слой повторного появления этого простого множителя.

Почему недостаточно числа кратных

В произведении от одного до двадцати кратные трём встречаются шесть раз. Но множитель девять содержит две тройки, как и восемнадцать. Поэтому показатель тройки в 20! больше шести. Первый подсчёт учитывает по одной тройке в каждом кратном, а следующий должен добавить вторые тройки из кратных девяти.

Именно поэтому складывают целые части делений на последовательные степени простого. Кратных p² среди чисел до n столько, сколько целая часть n/p². Они уже учтены на первом слое, но теперь получают необходимый дополнительный вклад. Кратные p³ добавляются ещё раз. Повторный учёт здесь намеренный и соответствует нескольким одинаковым простым множителям.

Послойный подсчёт без огромного произведения

Для 20! и p=3 имеем шесть кратных трём, два кратных девяти и ни одного кратного двадцати семи. Показатель равен восьми. Сам факториал вычислять не пришлось. Сумма всегда конечна: как только очередная степень p превосходит n, её целая часть и все дальнейшие вклады равны нулю.

Для отношения факториалов показатели вычитаются. Например, в числе сочетаний C(n,k)=n!/(k!(n−k)!) показатель p получается разностью трёх таких сумм. Для корректного целого сочетания результат неотрицателен. Если в произвольном отношении он отрицателен хотя бы для одного простого, отношение не является целым.

Пример

Каков показатель двойки в 18!?

Складываем целые части: 18/2 даёт 9, 18/4 даёт 4, 18/8 даёт 2, 18/16 даёт 1. Итого 16. Степень 32 уже больше 18 и ничего не добавляет.

Простое основание и составной делитель

Формула относится к простому p. Для наибольшей степени составного числа сначала раскладывают его на простые. Чтобы понять, сколько раз делится на двенадцать, сравнивают запас двоек и троек: на каждую двенадцатку нужны две двойки и одна тройка. Ответ задаёт меньший из соответствующих доступных количеств.

Число нулей в конце десятичной записи факториала — частный случай с основанием десять. Оно требует пар двойка-пятёрка, а не просто количества множителей десять в исходном списке. Поскольку двоек в факториале не меньше, ограничивают пятёрки. Объяснение через показатели позволяет перенести тот же принцип на другие основания без придумывания новой формулы.

От чтения к действию

А теперь — вы

Каков точный показатель пятёрки в 31!?

Частые вопросы

Что делать при n=0?

Поскольку 0!=1, показатель любого простого равен нулю. В сумме все целые части также нулевые.

Почему кратные квадрату простого учитывают дважды?

В них действительно есть как минимум два множителя p: первый посчитан на слое p, второй добавлен на слое p².

Источники и работа с материалом

Объяснение, примеры и вопросы написаны для erudeet. Факты и определения сверены по источникам ниже; это ссылки для самостоятельной проверки.

Продолжить разбираться