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

.

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

Якщо — просте число, тоді число ділиться на . Зворотньо: якщо ділиться на , тоді — просте число.

Історія

ред.

Теорема вперше була сформульована індійським математиком Бхаскарою, а згодом арабським вченим Ібн аль Хайтамом. В Європі її сформулював без доведення англійський математик Джон Вілсон, на честь якого вона названа. Перше відоме доведення дав Лагранж у 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;
}

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

Дивись також

ред.

Література

ред.

Українською

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

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

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