Задача
В Москве каждую секунду один из жителей ест печеньку. Докажите, что если бы собрать все печеньки, съеденные за 6 недель и одну секунду, то их можно было бы разделить на 11 равных кучек.
Решение. Прежде всего заметим, что в 6 неделях ровно 10! секунд. В самом деле,
в неделе 7 суток,
в сутках 24 = 3 · 8 часов,
в часе 3600 = 2 · 4 · 5 · 9 · 10 секунд,
так что 6 недель составляет 2 · 3 · 4 · 5 · 6 · 7 · 8 · 9 · 10 секунд.
Решение задачи основано на теореме Вильсона. Теорема утверждает:
если p — простое число, то число (p – 1)! +1 делится на p.
Доказательство теоремы Вильсона опирается на следующий важный факт:
все числа от 2 до p – 2 можно разбить на пары взаимно обратных по умножению чисел, то есть для каждого a из этого интервала найдётся такое b , что ab ≡ 1 (mod p).
Этот факт можно заключить, например, из Малой теоремы Ферма:
a·a ᵖ⁻ ² = a ᵖ ⁻¹ ≡ 1 (mod p). Но, учитывая, что он нередко используется для доказательства самой МТФ, можно просто заметить, что числа 0, a, 2a, ..., (p – 1)a при делении на p дают разные остатки:
ia – ja = (i – j)a не делится на p, поскольку |i – j| < p. Следовательно, эти остатки принимают все возможные значения, в том числе и 1.
Для доказательства теоремы Вильсона осталось перемножить все ненулевые остатки:
(p – 1)! ≡ p – 1 ≡ – 1 (mod p).
Теорема Вильсона была сформулирована Эдуардом Варингом в 1770 г., по его словам, она принадлежала его ученику Джону Вильсону, а доказана была Жозефом Луи Лагранжем в 1771 г.