Назад
Задача

Найдите остаток от деления числа 1000! на 10250.

Решение

  Назовём основными нечётные числа, не кратные 5. Согласно формуле из задачи 160553  1000! делится на  2994·5249 = 2745·10249.  Таким образом это чисдо оканчивается на 249 нулей, а нужно найти стоящую перед ними цифру. Представив каждое число от 1 до 1000 в виде 2m5na, где a – основное число, мы получим, что эта цифра совпадает с последней цифрой числа 2745P, где – произведение получившихся основных чисел. Заметим еще. что число

2745 = 2·16186  оканчивается двойкой, так что достаточно найти последнюю цифру числа 2P.

  Для пары  (m, n),  где  2m5n ≤ 1000,  в 1000! попадают множители вида 2m5na, где a – основные числа, не превосходящие  [1000·2m5n].  Их произведение обозначим Pm,n. Пусть P – произведение всех таких чисел Pm,n. Вычислим эти произведения.

  Сомножители P0,0 – все основные числа от 1 до 1000. Среди них по 100 чисел, оканчивающихся на 1, 3, 5, 7. Поскольку  3·7 ≡ 9·9 ≡ 1 (mod 10),

P0,0 ≡ 1 (mod 10).

  Сомножители P1,0 – все основные числа от 1 до 499. Аналогично P1,0 ≡ 1 (mod 10).

  С P2,0 (основные числа, меньшие 250) ситуация меняется: для числа 253 нет парной семёрки  (257 > 250).  Поэтому  P2,0 ≡ 3 (mod 10).

  Также и  P3,0 ≡ 3 (mod 10)  (для 123 нет парной семёрки).

  P4,0 ≡ 1 (mod 10)  (основные числа от 1 до 61).

  P5,0 ≡ 9 (mod 10)  (основные числа от 1 до 31, количество девяток нечётно).

  P6,0 ≡ 3·9 (mod 10)  (основные числа – 1, 3. 7, 9, 11, 13).

  P7,0 ≡ 1 (mod 10)  (основные числа – 1, 3 и 7).

  P8,0 = 3 (mod 10)  (основные числа – 1 и 3).

  P9,0 = 9 (mod 10)  (здесь единственное основное число – 1).

  P0,1 ≡ 1 (mod 10)   (основные числа, меньшие 200).

  P1,1 ≡ 1 (mod 10)  (основные числа, меньшие 100).

  P1,2 ≡ 9 (mod 10)  (основные числа от 1 до 49, количество девяток нечётно).

  P1,3 ≡ 3 (mod 10)  (основные числа от 1 до 25).

  P1,4 ≡ 9 (mod 10)  (основные числа – 1, 3. 7, 9, 11).

  P1,5 = 3 (mod 10)  (основные числа – 1, 3).

  P1,6 = 3  (основные числа – 1, 3).

  P1,7 = 1  (единственное основное число – 1).

  P0,2 ≡ 1 (mod 10)  (основные числа, меньшие 40).

  P1,2 ≡ 1 (mod 10)  (основные числа, меньшие 20).

  P2,2 ≡ 9 (mod 10)  (основные числа – 1, 3, 7, 9).

  P3,2 = 3 (mod 10)  (основные числа – 1, 3).

  P3,2 = 1 (единственное основное число – 1).

  P0,3 ≡ 1 (mod 10)  (основные числа – 1, 3, 7).

  P1,3 = 3 (mod 10)  (основные числа – 1, 3).

  P2,3 = P3,3  (единственное основное число – 1).

  Итак,  P ≡ 38·96 = 910 ≡ 1 (mod 10),  то есть число 2P оканчивается двойкой.

Ответ

2·10249.

Чтобы оставлять комментарии, войдите или зарегистрируйтесь

Комментариев нет