Теорема Вілсона

В теорії чисел теорема Вілсона стверджує, що натуральне число $n>1$ є простим в тому і тільки тому випадку коли справджується рівність:

$(n-1)!\equiv -1modn$.

Або ж, в словесному формулюванні: Шаблон:Теорема

Історія

Теорема вперше була сформульована індійським математиком Бхаскарою, а згодом арабським вченим Ібн аль Хайтамом. В Європі її сформулював без доведення англійський математик Джон Вілсон, на честь якого вона названа. Перше відоме доведення дав Лагранж у 1773 році.

Доведення

Нехай $p$ деяке просте число. Елементарними обчисленнями можна переконатися, що теорема справджується для $p=2$ і $p=3$. Тож вважатимемо, що $p>3$. Якщо для деякого цілого справджується рівність:

$x^2\equiv 1modp$,

то справджується також $x^2-1\equiv 0modp$, або

$(x-1)\cdot (x+1)\equiv 0modp$,

Тож у випадку, якщо $1<x<p-1$, маємо $x=1$ або $x=p-1$.

Якщо ж $2<x<p-2$, тоді існує деяке $2<y<p-2$, відмінне від $x$, таке, що $xy\equiv 1modp$. Таким чином справджується:

$2\cdot ...\cdot (p-2)\equiv 1modp$.

Дана рівність еквівалентна наступній:

$1\cdot ...\cdot (p-1)\equiv p-1modp$,

звідки випливає, що $(p-1)!+1$ ділиться на $p$. Тоді $a|(p-1)!$ і як наслідок

$a\cdot b|(p-1)!\cdot b$

зважаючи, що $p=a\cdot b$ маємо

$(p-1)!\cdot b\equiv 0modp$,

звідки

$(p-1)!\cdot b\equiv ̸(-1)\cdot bmodp$.

Тому маємо

$(p-1)!\equiv ̸-1modp$

і число $(p-1)!+1$ не ділиться на $p$.

Застосування теореми

Теорема Вілсона може бути використана для перевірки чисел на простоту. Наприклад відповідний алгоритм на мові С++:

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;
}

Проте через складність обчислення факторіалу даний метод є дуже неефективним.

Дивись також

• Мала теорема Ферма
• Китайська теорема про залишки
• Модульна арифметика
• Факторіал
• Теорема Волстенголма

Література

Українською

• Шаблон:Ref-uk Шаблон:Книга

Іншими мовами

• Бухштаб А. А. Теория чисел, 2-е издание, М., 1966
• Трост Э. Простые числа, пер. с нем., М., 1959