В теорії чисел теорема Вілсона стверджує, що натуральне число є простим в тому і тільки тому випадку коли справджується рівність: . Або ж, в словесному формулюванні:
Історія Теорема вперше була сформульована індійським математиком Бхаскарою, а згодом арабським вченим Ібн аль Хайтамом. В Європі її сформулював без доведення англійський математик Джон Вілсон, на честь якого вона названа. Перше відоме доведення дав Лагранж у 1773 році.
Доведення
Нехай деяке просте число. Елементарними обчисленнями можна переконатися, що теорема справджується для і . Тож вважатимемо, що . Якщо для деякого цілого справджується рівність:
, то справджується також , або , Тож у випадку, якщо , маємо або .
Якщо ж , тоді існує деяке , відмінне від , таке, що . Таким чином справджується: . Дана рівність еквівалентна наступній: , звідки випливає, що ділиться на . Тоді і як наслідок
зважаючи, що маємо , звідки . Тому маємо
і число не ділиться на .
Застосування теореми Теорема Вілсона може бути використана для перевірки чисел на простоту. Наприклад відповідний алгоритм на мові С++: int factorial(int x) { if( x == 0 ) return 1; return x * factorial (x - 1) % p; } bool simpleInt (int p) { return (factorial (p-1)+1)%p==0; } Проте через складність обчислення факторіалу даний метод є дуже неефективним.
Дивись також Мала теорема Ферма Китайська теорема про залишки Модульна арифметика Факторіал Теорема Волстенголма
Література Українською
Іншими мовами Бухштаб А. А. Теория чисел, 2-е издание, М., 1966 Трост Э. Простые числа, пер. с нем., М., 1959