Введение

Теорема о простых числах
В алгебре и теории чисел теорема Уилсона утверждает, что натуральное число n > 1 является простым тогда и только тогда, когда произведение всех натуральных чисел, меньших n, на единицу меньше кратного n. То есть (используя обозначения модульной арифметики), факториал удовлетворяет следующему условию:

точно тогда, когда n является простым числом. Иными словами, любое целое число n > 1 является простым, если и только если (n − 1)! + 1 делится на n.

История

Теорема была впервые сформулирована Ибн аль-Хайтамом примерно в 1000 году нашей эры. Эдвард Уоринг объявил об этой теореме в 1770 году, не предоставив доказательства, и указал, что открытие принадлежит его ученику Джону Уилсону. Лагранж представил первое доказательство в 1771 году. Существуют свидетельства того, что Лейбниц также был знаком с этим результатом за столетие до этого, но не опубликовал его.

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

В доказательствах (для простых модулей), представленных ниже, используется тот факт, что классы вычетов по простому модулю образуют конечное поле – подробности см. в статье «Простое поле». Для всех доказательств требуется теорема Лагранжа, утверждающая, что в любом поле многочлен степени n имеет не более n корней.

Композитный модуль

Если n – составное число, то оно делится на некоторое простое число q, где 2 ≤ q ≤ n − 2. Поскольку q делит n, то q делит (n − 1)!, то есть (n − 1)! = kq для некоторого целого k. Предположим для противоречия, что (n − 1)! ≡ −1 (mod n), где n – составное число. Тогда (n − 1)! также будет сравнимо с −1 (mod q), так как (n − 1)! ≡ −1 (mod n) подразумевает (n − 1)! ≡ −1 (mod q) для некоторого целого k, что показывает (n − 1)! ≡ 1 (mod q). Но (n − 1)! ≡ 0 (mod q) по тому факту, что q является одним из множителей в произведении (n − 1)! = 1 × 2 × … × (n − 1), то есть (n − 1)! кратно q. Это приводит к противоречию. Более того, верно следующее: за исключением случая n = 4, где 3! = 6 ≡ 2 (mod 4), если n – составное число, то (n − 1)! ≡ 0 (mod n). Доказательство разбивается на два случая: во-первых, если n можно представить в виде произведения двух различных чисел, то есть n = ab, где 2 ≤ a < b ≤ n − 2, то и a, и b будут присутствовать в произведении 1 × 2 × … × (n − 1) = (n − 1)!, и, следовательно, (n − 1)! будет делиться на n. Если n не имеет такой факторизации, то оно должно быть квадратом некоторого простого числа q, где q > 2. Но тогда 2q < q² = n, и как q, так и 2q будут множителями (n − 1)!, а значит, n делит (n − 1)!.

Испытания первичности

На практике теорема Уилсона неэффективна в качестве теста на простоту, поскольку вычисление (n − 1)! по модулю n для больших n является вычислительно сложной задачей, и существуют гораздо более быстрые тесты на простоту (фактически, даже пробное деление значительно эффективнее). При использовании в обратном направлении, для определения простоты чисел, следующих за большими факториалами, это действительно очень быстрый и действенный метод. Однако практическая ценность этого невелика.

Формулы простых чисел

Теорема Уилсона использовалась для построения формул для простых чисел, но они слишком медленные для практического применения.

p-адная гамма-функция

Теорема Уилсона позволяет определить p-адическую гамма-функцию.