Вильсон теоремасы сандар теориясындағы теорема p сонда тек сонда егер p 1 1 displaystyle p 1 1 p ға бөлінсе ғана жай сан

Вильсон теоремасы — сандар теориясындағы теорема:

p — сонда, тек сонда егер $(p-1)!+1$ p-ға бөлінсе ғана жай сан болады

Тарихы

Теореманы алғашқы рет 1770 жылы тұжырымдаған, әрі оның сөзіне қарағанда тиесілі болған. 1771 жылы дәлелдеген.

C++ тіліндегі коды

int factorialMod(int x, int p) {  if( x == 0 ) return 1;  return (x * factorialMod(x-1,p)) % p; } bool primeInt (int p) {  return (factorialMod(p-1,p)+1)%p == 0; }

Мұндағы factorialMod(x,p) функция x санының p модулі бойынша факториалын еcептейді, ал primeInt(x) функциясы мәні —false, егер x құрама болса, true, егер жай болса.

Әдебиет

Бухштаб А. А. Теория чисел, 2-е издание, М., 1966
Трост Э. Простые числа, пер. с нем., М., 1959
Виноградов И. М. Основы теории чисел — 5 изд.. — Мәскеу: Гостехиздат, 1952.