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

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

.

Історія

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

Доведення

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

,

то справджується також , або

,

Тож у випадку, якщо , маємо або .

Якщо ж , тоді існує деяке , відмінне від , таке, що . Таким чином справджується:

.

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

,

звідки випливає, що ділиться на . Тоді і як наслідок

зважаючи, що маємо

,

звідки

.

Тому маємо

і число не ділиться на .

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

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

int factorial(int x) {
    if( x == 0 ) return 1;
    return x * factorial (x - 1);
}
bool simpleInt (int p)
{
  return ((factorial (p-1)+1)%p==0);
}

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

Дивись також

Література

  • Бухштаб А. А. Теория чисел, 2-е издание, М., 1966
  • Трост Э. Простые числа, пер. с нем., М., 1959
This article is issued from Wikipedia. The text is licensed under Creative Commons - Attribution - Sharealike. Additional terms may apply for the media files.