Теорема Вильсона — это интересный математический факт, но НЕ инструмент для решения стандартных задач. Её достаточно понимать на уровне примеров. Если вы участвуете в олимпиадах — изучите её как «лайфхак» для задач на делимость.
Теорема Вильсона названа в честь английского математика Джона Вильсона (1741–1793), хотя он не был её первооткрывателем и не смог её доказать.
В 1770 году английский математик Эдвард Варинг (Edward Waring) опубликовал её как гипотезу своего ученика Джона Вильсона. Полное и строгое доказательство теоремы впервые дал в 1771 году Жозеф Луи Лагранж.
Теорема Вильсона:
Натуральное число \( p >1 \) является простым тогда и только тогда, когда
\( (p - 1)! \equiv -1 \pmod{p} \)
Это эквивалентно: остаток от деления \( (p - 1)! \) на \( p \) равен \( p - 1 \).
Следствие: если \( p \) — простое и \( p > 2 \), то
\( (p - 2)! \equiv 1 \pmod{p} \)
Важно: для составных \( p \ne 4 \) выполняется \( (p - 1)! \equiv 0 \pmod{p} \). Для \( p = 4 \): \( 3! = 6 \equiv 2 \pmod{4} \).
- Определите: дано \( (p - 1)! \) или \( (p - 2)! \)?
- Проверьте, простое ли число \( p \) (в задачах обычно даётся простое).
- Если дано \( (p - 1)! \):
- Ответ: \( p - 1 \) (так как \( -1 \equiv p - 1 \pmod{p} \)).
- Если дано \( (p - 2)! \):
- Используйте: \( (p - 1)! = (p - 1) \cdot (p - 2)! \equiv -1 \pmod{p} \).
- Так как \( p - 1 \equiv -1 \pmod{p} \), то \( (-1) \cdot (p - 2)! \equiv -1 \).
- Разделите обе части на \( -1 \): \( (p - 2)! \equiv 1 \pmod{p} \).
- Если модуль — составное число (редко в задачах):
- Для \( n \geq 6 \) составного: \( (n - 1)! \equiv 0 \pmod{n} \).
Пример 1. \( 6! \bmod 7 \): \( p = 7 \) — простое, \( 6! = (7 - 1)! \Rightarrow 6! \equiv -1 \equiv 6 \pmod{7} \).
Пример 2. \( 5! \bmod 7 \): \( p = 7 \), \( 5! = (7 - 2)! \Rightarrow 5! \equiv 1 \pmod{7} \).
Пример 3. \( 4! \bmod 5 \): \( 4! = 24 \equiv -1 \equiv 4 \pmod{5} \) — верно, 5 — простое.
Пример 4. \( 8! \bmod 9 \): 9 — составное, \( 8! \) содержит 3 и 6 ⇒ делится на 9 ⇒ остаток 0.
Нажмите «Новое задание» для начала.