Всякое натуральное число m можно, и притом единственным способом, разложить на простые множители. Очевидно, показатель степени a, с которым простое число p входит в разложение числа m на простые множители: m = p₁^a₁·p₂^a₂·. . .p_k^a_k, равен максимальной степени числа p, на которое делится m.

Возьмём число N! = 1·2·...·N. Пусть p - некоторое простое число. Как узнать: на какую максимальную степень числа p делится N!?

Посчитаем, сколько в последовательности 1, 2, ..., N чисел, кратных p. Если таких чисел k, то число kp среди них - наибольшее, и поэтому kp Ј N < (k+1)p, т.е. k Ј N/p < k+1. Значит, k = [N/p].

Итак, среди чисел 1, 2, ..., N кратными p будут числа p, 2p, 3p,:, [N/p]p, и мы можем записать N! так:

где число M₁ на p уже не делится. Если [N/p] < p, то максимальная степень числа p, на которую делится N!, равна [N/p]. Если же [N/p ] і p,. то выделим числа, кратные числу p, среди чисел 1, 2, . . . , [N/p ]. Их будет [[([N/p])/( p)] ], или (свойство 5) - [[(N)/( p²)]]. Таким образом,

Через конечное число шагов мы получим степень p^s, большую N; т.е. [[(N)/( p^s)]] = 0. Следовательно, в сумме (3) число слагаемых - конечное, и мы можем дать окончательный ответ: простое число p входит в разложение числа N! с показателем

Применим полученную формулу к решению следующих задач.

Пример 20. Сколькими нулями оканчивается число 1996!?
Решение Задача будет решена, если мы найдём, чему равна максимальная степень числа 10, на которую делится 1996!. Но поскольку 10 = 5·2, нам достаточно подсчитать, в какой степени число 5 входит в разложение на простые множители числа 1996! (ясно, что 2 войдёт в 1996! сомножителем большее число раз, нежели 5). Так как 5⁴ < 1996 < 5⁵, то мы получаем следующий ответ: число 1996! оканчивается

Пример 21.Доказать, что число C⁹⁷⁶₁₉₇₆ делится на 76².
Решение Поскольку 76 = 2²·19, то для делимости на 76² необходимо и достаточно, чтобы C⁹⁷⁶₁₉₇₆ делилось на 2⁴ и 19². Имеем C⁹⁷⁶₁₉₇₆ = [1976!/ 976!·1000!]. Найдём, чему равны показатели степеней a₁, a₂, a₃ и b₁, b₂, b₃, с которыми числа 2 и 19 входят в разложения на простые множители чисел 19761, 976! и 1000!. Имеем

и a₁-a₂-a₃ = 4, то есть C⁹⁷⁶₁₉₇₆ делится на 2⁴.

Аналогично

Пример 22. Докажите, что для любого действительногочисла a разность ([a]/ 1997)-([a/1997]) может принимать только значения 0, 1/1997, 2/1997, ..., 1996/1997.
Решение Для любого a имеем a-1 < [a] Ј a, так что