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

Матеріал з Вікіпедії — вільної енциклопедії.
Перейти до: навігація, пошук

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

(n-1)!\ \equiv\ -1\ \mod n

Історія[ред.ред. код]

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

Доведення[ред.ред. код]

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

x^2 \equiv 1\mod p,

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

(x - 1)\cdot(x+1) \equiv 0 \mod p,

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

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

2\cdot ... \cdot (p-2) \equiv 1 \mod p.

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

1\cdot ... \cdot(p-1) \equiv p-1 \mod p,

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

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

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

(p-1)!\cdot b \equiv\; 0\mod p,

звідки

(p-1)!\cdot b\not\equiv (-1)\cdot b\mod p.

Тому маємо

 (p-1)!\ \not\equiv\ -1 \mod p\,

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

Застосування теореми[ред.ред. код]

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

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