Теорема Вильсона - Википедия - Wilsons theorem

В теория чисел, Теорема Вильсона заявляет, что натуральное число п > 1 - это простое число если и только если продукт всех положительные целые числа меньше, чем п на единицу меньше, чем кратное п. То есть (используя обозначения модульная арифметика ), факториал удовлетворяет

когда именно п простое число. Другими словами, любое число п является простым числом тогда и только тогда, когда (п - 1)! + 1 делится на п.[1]

История

Эта теорема была сформулирована Ибн аль-Хайсам (ок. 1000 г. н.э.),[2] а в 18 веке Джон Уилсон.[3] Эдвард Уоринг объявил теорему в 1770 году, хотя ни он, ни его ученик Вильсон не смогли ее доказать. Лагранж дал первое доказательство в 1771 году.[4] Есть свидетельства того, что Лейбниц также знал о результате столетием раньше, но никогда не публиковал его.[5]

Пример

Для каждого из значений п от 2 до 30 в следующей таблице указано число (п - 1)! а остальное при (п - 1)! делится на п. (В обозначениях модульная арифметика, остаток при м делится на п написано м мод п.) Цвет фона синий для основной ценности п, золото для составной значения.

Таблица факториала и его остаток по модулю п

(последовательность A000142 в OEIS )

(последовательность A061006 в OEIS )
211
322
462
5244
61200
77206
850400
9403200
103628800
11362880010
12399168000
1347900160012
1462270208000
15871782912000
1613076743680000
172092278988800016
183556874280960000
19640237370572800018
201216451004088320000
2124329020081766400000
22510909421717094400000
23112400072777760768000022
24258520167388849766400000
256204484017332394393600000
26155112100433309859840000000
274032914611266056355840000000
28108888694504183521607680000000
2930488834461171386050150400000028
3088417619937397019545436160000000

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

Оба приведенных ниже доказательства (для простых модулей) используют тот факт, что классы вычетов по модулю простого числа являются поле —Смотрите статью основное поле Больше подробностей.[6] Теорема Лагранжа, который утверждает, что в любом поле a многочлен из степень п имеет самое большее п корни, требуется для обоих доказательств.

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

Если п составно делится на некоторое простое число q, куда 2 ≤ qп − 2. Если (п − 1)! соответствовали −1 (mod п) то оно также было бы конгруэнтно −1 (mod q). Но (п - 1)! ≡ 0 (модq).

На самом деле, правда больше. За исключением 4, где 3! = 6 ≡ 2 (mod 4), если п составно, то (п - 1)! конгруэнтно 0 (modп). Доказательство разбивается на два случая: во-первых, если п можно разложить на множители как произведение двух неравных чисел, п = ab, где 2 ≤а < б ≤ п - 2, затем оба а и б появится в продукте 1 × 2 × ... × (п − 1) = (п − 1)! и (п - 1)! будет делиться на п. Если п не имеет такой факторизации, то это должен быть квадрат некоторого простого q, q > 2. Но тогда 2q < q2 = п, обе q и 2q будут факторы (п - 1) !, и снова п делит (п − 1)!.

Основной модуль

Элементарное доказательство

Результат тривиален, когда п = 2так что предположим п нечетное простое число, п ≥ 3. Поскольку классы вычетов (mod п) - поле, каждое ненулевое а имеет единственный мультипликативный обратный, а−1. Теорема Лагранжа означает, что единственные значения а для которого аа−1 (мод п) находятся а ≡ ± 1 (мод. п) (потому что соответствие а2 ≡ 1 может иметь не более двух корней (mod п)). Следовательно, за исключением ± 1, множители (п − 1)! могут быть расположены неравными парами,[7] где произведение каждой пары ≡ 1 (мод п). Это доказывает теорему Вильсона.

Например, если п = 11,

Доказательство с помощью маленькой теоремы Ферма.

Опять же, результат тривиален для п = 2, поэтому предположим п нечетное простое число, п ≥ 3. Рассмотрим многочлен

грамм имеет степень п − 1, ведущий термин Иксп − 1, и постоянный член (п − 1)!. Его п − 1 корни 1, 2, ..., п − 1.

Теперь рассмотрим

час также имеет степень п − 1 и ведущий термин Иксп − 1. По модулю п, Маленькая теорема Ферма говорит, что у него тоже есть п − 1 корни, 1, 2, ..., п − 1.

Наконец, рассмотрим

ж имеет высшее образование п - 2 (так как главные члены сокращаются) и по модулю п также имеет п − 1 корни 1, 2, ..., п − 1. Но теорема Лагранжа говорит, что не может быть больше, чем п - 2 корня. Следовательно, ж должен быть тождественно нулем (mod п), поэтому его постоянный член (п - 1)! + 1 ≡ 0 (мод п). Это теорема Вильсона.

Доказательство с использованием теорем Силова.

Можно вывести теорему Вильсона из конкретного приложения Теоремы Силова. Позволять п быть первым. Сразу можно сделать вывод, что симметричная группа точно элементы порядка п, а именно п-циклы . С другой стороны, каждый силовский п-подгруппа в это копия . Отсюда следует, что число силовских п-подгруппы . Из третьей теоремы Силова следует

Умножая обе стороны на (п − 1) дает

то есть результат.

Приложения

Тесты на первичность

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

Квадратичные вычеты

Используя теорему Вильсона, для любого нечетного простого числа п = 2м + 1, мы можем переставить левую часть

чтобы получить равенство

Это становится

или же

Мы можем использовать этот факт, чтобы доказать часть известного результата: для любого простого числа п такой, что п ≡ 1 (мод.4) число (−1) представляет собой квадрат (квадратичный вычет ) мод п. Предположим п = 4k + 1 для некоторого целого числа k. Тогда мы можем взять м = 2k выше, и мы заключаем, что (м!)2 конгруэнтно (−1).

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

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

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

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

Обобщение Гаусса

Гаусс доказал, что[8]

куда п представляет собой нечетное простое число и положительное целое число. Ценности м для которых произведение равно −1, - это в точности те, для которых существует примитивный корень по модулю м.

Это далее обобщает тот факт, что в любом конечный абелева группа, либо произведение всех элементов является единицей, либо существует ровно один элемент а из порядок 2 (но не оба). В последнем случае произведение всех элементов равноа.

Смотрите также

Примечания

  1. ^ Универсальная книга математики. Дэвид Дарлинг, стр. 350.
  2. ^ О'Коннор, Джон Дж.; Робертсон, Эдмунд Ф., «Абу Али аль-Хасан ибн аль-Хайтам», Архив истории математики MacTutor, Сент-Эндрюсский университет.
  3. ^ Эдвард Уоринг, Meditationes Algebraicae (Кембридж, Англия: 1770), стр. 218 (на латыни). В третьем (1782 г.) издании Уоринга Meditationes Algebraicae, Теорема Вильсона появляется как проблема 5 на стр. 380. На этой странице Уоринг заявляет: «Hanc maxime elegantem primorum numerorum proprietatem invenit vir claissimus, rerumque mathematicarum peritissimus Joannes Wilson Armiger». (Самый выдающийся и наиболее опытный в математике человек, сквайр Джон Уилсон, обнаружил это самое элегантное свойство простых чисел.)
  4. ^ Жозеф Луи Лагранж, "Demonstration d'un théorème nouveau Concernt les nombres premiers" (Доказательство новой теоремы о простых числах), Nouveaux Mémoires de l'Académie Royale des Sciences et Belles-Lettres (Берлин), т. 2, страницы 125–137 (1771).
  5. ^ Джованни Вакка (1899) "Sui manoscritti inediti di Leibniz" (О неопубликованных рукописях Лейбница),Bollettino di bibliografia e storia delle scienze matematiche ... (Вестник библиографии и истории математики), т. 2, страницы 113–116; видеть стр. 114 (на итальянском). Цитаты Вакки из математических рукописей Лейбница, хранящихся в Королевской публичной библиотеке в Ганновере (Германия), т. 3 Б, пачка 11, стр.10:

    Оригинал : Inoltre egli intravide anche il teorema di Wilson, come risulta dall'enunciato seguente:

    «Productus continorum usque ad numerum qui antepraecedit datum divisus per datum reinquit 1 (vel complementum ad unum?) Si datus sit primitivus. Si datus sit Derivativus relinquet numerum qui cum dato habeat communem mensuram unitate majorem».

    Egli non giunse pero a dimostrarlo.

    Перевод : Кроме того, он [Лейбниц] также ознакомился с теоремой Вильсона, как показано в следующем утверждении:

    "Произведение всех целых чисел, предшествующих данному целому числу, при делении на данное целое число, оставляет 1 (или дополнение к 1?), Если данное целое число является простым. Если данное целое число является составным, остается число, имеющее общее множитель с заданным целым числом, [которое] больше единицы ".

    Однако доказать это ему не удалось.

    См. Также: Джузеппе Пеано, изд., Formulaire de mathématiques, т. 2, вып. 3, стр. 85 (1897).
  6. ^ Ландау, два доказательства этого. 78
  7. ^ Когда п = 3, единственными множителями являются ± 1
  8. ^ Гаусс, Д.А., арт. 78

Рекомендации

В Disquisitiones Arithmeticae был переведен с цицероновской латыни Гаусса на английский и немецкий языки. Немецкое издание включает в себя все его работы по теории чисел: все доказательства квадратичной взаимности, определение знака суммы Гаусса, исследования биквадратичной взаимности и неопубликованные заметки.

  • Гаусс, Карл Фридрих; Кларк, Артур А. (1986), Disquisitiones Arithemeticae (2-е исправленное изд.), Нью-Йорк: Springer, ISBN  0-387-96254-9 (переведено на английский).
  • Гаусс, Карл Фридрих; Мазер, Х. (1965), Untersuchungen über hohere Arithmetik (Disquisitiones Arithemeticae и другие статьи по теории чисел) (2-е изд.), Нью-Йорк: Челси, ISBN  0-8284-0191-8 (переведено на немецкий язык).
  • Ландау, Эдмунд (1966), Элементарная теория чисел, Нью-Йорк: Челси.
  • Оре, Ойштейн (1988). Теория чисел и ее история. Дувр. стр.259–271. ISBN  0-486-65620-9.

внешняя ссылка