Теорема Вильсона

#АПО_математика #Вильсон #Теорема_Вильсона

 

После более чем месячного перерыва #АПО_математика возвращается! На этот раз - известное и полезное утверждение из теории чисел, называемое теоремой Вильсона. В соответствии с "принципом Арнольда" теорема принадлежит вовсе не Вильсону: её впервые сформулировал (без доказательства) Уоринг (его портрет прикреплён к посту) в 1770 году в своем сочинении «Meditationes Algebraicae». Первое доказательство теоремы Вильсона было дано в 1771 году Лагранжем. Давайте в нём разберёмся.

 

Теорема Вильсона:

Натуральное число p > 1 является простым тогда и только тогда, когда (p−1)!+1 делится на p (здесь N! (читается "N-факториал") обозначает произведение всех натуральных чисел от 1 до N.

 

Доказательство:

 

Необходимость:

Пусть p - простое. Рассмотрим (p-1)!. Для каждого ненулевого остатка a по модулю p существует единственный остаток b (называемый обратным) такой, что ab ≡ 1 (mod p). Действительно, поскольку a и p взаимно просты (так как p - простое, а a меньше p), то множества остатков {1, 2, ..., p-1} и {1*a, 2*a, ..., (p-1)*a} совпадают, то есть существует b такой, что ab ≡ 1 (mod p). Если b1 и b2 удовлетворяют этому условию, то ab1-ab2 делится на p, то есть b1-b2 делится на p, и, поскольку b1 и b2 меньше p, то b1=b2.

Значит, все ненулевые остатки по модулю p разбиты на пары обратных, кроме тех, для которых обратный ему равен. Таких ровно два - 1 и -1 (если a - такой остаток, то a*a ≡ 1 (mod p), то есть a*a-1 делится на p, то есть (a-1)*(a+1) делится на p, а значит, a-1 делится на p или a+1 делится на p). Следовательно, поскольку произведение обратных остатков равно 1, то (p-1)! ≡ 1*...*1*1*(-1) ≡ -1 (mod p).

 

Достаточность:

Если n составное и n ≠ 4, то (n−1)! ≡ 0 (mod n), а при n = 4 получаем (4−1)! ≡ 2 (mod 4).

 

Теорема доказана.