Задача 60829

Темы:    [ Арифметика остатков (прочее) ] [ Произведения и факториалы ]

Сложность: 4 Классы: 8,9,10

Условие

Найдите остаток от деления числа 1000! на 10²⁵⁰.

Решение

  Назовём основными нечётные числа, не кратные 5. Согласно формуле из задачи 60553  1000! делится на  2⁹⁹⁴·5²⁴⁹ = 2⁷⁴⁵·10²⁴⁹.  Таким образом это чисдо оканчивается на 249 нулей, а нужно найти стоящую перед ними цифру. Представив каждое число от 1 до 1000 в виде 2^m5ⁿa, где a – основное число, мы получим, что эта цифра совпадает с последней цифрой числа 2⁷⁴⁵P, где – произведение получившихся основных чисел. Заметим еще. что число
2⁷⁴⁵ = 2·16¹⁸⁶  оканчивается двойкой, так что достаточно найти последнюю цифру числа 2P.
  Для пары  (m, n),  где  2^m5ⁿ ≤ 1000,  в 1000! попадают множители вида 2^m5ⁿa, где a – основные числа, не превосходящие  [1000·2^–m5^–n].  Их произведение обозначим P_m,n. Пусть P – произведение всех таких чисел P_m,n. Вычислим эти произведения.
  Сомножители P_0,0 – все основные числа от 1 до 1000. Среди них по 100 чисел, оканчивающихся на 1, 3, 5, 7. Поскольку  3·7 ≡ 9·9 ≡ 1 (mod 10),
P_0,0 ≡ 1 (mod 10).
  Сомножители P_1,0 – все основные числа от 1 до 499. Аналогично P_1,0 ≡ 1 (mod 10).
  С P_2,0 (основные числа, меньшие 250) ситуация меняется: для числа 253 нет парной семёрки  (257 > 250).  Поэтому  P_2,0 ≡ 3 (mod 10).
  Также и  P_3,0 ≡ 3 (mod 10)  (для 123 нет парной семёрки).
  P_4,0 ≡ 1 (mod 10)  (основные числа от 1 до 61).
  P_5,0 ≡ 9 (mod 10)  (основные числа от 1 до 31, количество девяток нечётно).
  P_6,0 ≡ 3·9 (mod 10)  (основные числа – 1, 3. 7, 9, 11, 13).
  P_7,0 ≡ 1 (mod 10)  (основные числа – 1, 3 и 7).
  P_8,0 = 3 (mod 10)  (основные числа – 1 и 3).
  P_9,0 = 9 (mod 10)  (здесь единственное основное число – 1).
  P_0,1 ≡ 1 (mod 10)   (основные числа, меньшие 200).
  P_1,1 ≡ 1 (mod 10)  (основные числа, меньшие 100).
  P_1,2 ≡ 9 (mod 10)  (основные числа от 1 до 49, количество девяток нечётно).
  P_1,3 ≡ 3 (mod 10)  (основные числа от 1 до 25).
  P_1,4 ≡ 9 (mod 10)  (основные числа – 1, 3. 7, 9, 11).
  P_1,5 = 3 (mod 10)  (основные числа – 1, 3).
  P_1,6 = 3  (основные числа – 1, 3).
  P_1,7 = 1  (единственное основное число – 1).
  P_0,2 ≡ 1 (mod 10)  (основные числа, меньшие 40).
  P_1,2 ≡ 1 (mod 10)  (основные числа, меньшие 20).
  P_2,2 ≡ 9 (mod 10)  (основные числа – 1, 3, 7, 9).
  P_3,2 = 3 (mod 10)  (основные числа – 1, 3).
  P_3,2 = 1 (единственное основное число – 1).
  P_0,3 ≡ 1 (mod 10)  (основные числа – 1, 3, 7).
  P_1,3 = 3 (mod 10)  (основные числа – 1, 3).
  P_2,3 = P_3,3  (единственное основное число – 1).
  Итак,  P ≡ 3⁸·9⁶ = 9¹⁰ ≡ 1 (mod 10),  то есть число 2P оканчивается двойкой.

Ответ

2·10²⁴⁹.

Источники и прецеденты использования

книга
Автор	Алфутова Н.Б., Устинов А.В.
Год издания	2002
Название	Алгебра и теория чисел
Издательство	МЦНМО
Издание	1
глава
Номер	4
Название	Арифметика остатков
Тема	Деление с остатком. Арифметика остатков
параграф
Номер	6
Название	Китайская теорема об остатках
Тема	Деление с остатком. Арифметика остатков
задача
Номер	04.203