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

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

${\displaystyle (n-1)!\ \equiv \ -1\ \mod n}$.

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

Якщо ${\displaystyle p}$ — просте число, тоді число ${\displaystyle (p-1)!+1}$ ділиться на ${\displaystyle p}$. Зворотньо: якщо ${\displaystyle (p-1)!+1}$ ділиться на ${\displaystyle p}$, тоді ${\displaystyle p}$ — просте число.

Історія

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

Доведення

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

${\displaystyle x^{2}\equiv 1\mod p}$,

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

${\displaystyle (x-1)\cdot (x+1)\equiv 0\mod p}$,

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

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

${\displaystyle 2\cdot ...\cdot (p-2)\equiv 1\mod p}$.

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

${\displaystyle 1\cdot ...\cdot (p-1)\equiv p-1\mod p}$,

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

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

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

${\displaystyle (p-1)!\cdot b\equiv 0\mod p}$,

звідки

${\displaystyle (p-1)!\cdot b\not \equiv (-1)\cdot b\mod p}$.

Тому маємо

${\displaystyle (p-1)!\ \not \equiv \ -1\mod p}$

і число ${\displaystyle (p-1)!+1\;}$ не ділиться на ${\displaystyle 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; } 

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

Дивись також

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

Література

Українською

• (укр.) Елементи теорії груп та теорії кілець. — І.-Ф.  : Голіней, 2023. — 153 с.

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

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