قضیه ویلسون

۱_تعمیم گاوس: کارل فریدریش گاوس ریاضی‌دان آلمانی در سال ۱۸۰۰ میلادی ثابت کرده که برای هر عدد طبیعی ${\displaystyle m>2}$

در اینجا ${\displaystyle \alpha }$

${\displaystyle (3-1)!=1\times 2=2\equiv -1(\mathrm{mod}3)}$

${\displaystyle (5-1)!=1\times 2\times 3\times 4=24\equiv -1(\mathrm{mod}5)}$

${\displaystyle (7-1)!=1\times 2\times 3\times 4\times 5\times 6=720\equiv -1(\mathrm{mod}7)}$

${\displaystyle (11-1)!=1\times 2\times 3\times 4\times 5\times 6\times 7\times 8\times 9\times 10=3628800\equiv -1(\mathrm{mod}11)}$

${\displaystyle (13-1)!=1\times 2\times 3\times 4\times 5\times 6\times 7\times 8\times 9\times 10\times 11\times 12=479001600\equiv -1(\mathrm{mod}13)}$

برهان اول

چون ${\displaystyle p}$

${\displaystyle (p-1)!\equiv 1\times \underbrace{2\times \mathrm{3...}\times (p-2)}\times (p-1)\equiv 1\times \underbrace{1\times \mathrm{1...}\times 1}\times (p-1)\equiv -1(\mathrm{mod}p)}$

تعیین اول بودن عدد

در عمل این الگوریتم برای تعیین اول بودن عدد ناکارآمد است؛ زیرا محاسبه ${\displaystyle (n-1)!modb}$

با اعمال قضیۀ ویلسون بر تمام اعداد اول فرد ${\displaystyle p=2m+1}$

${\displaystyle 1\cdot (p-1)\cdot 2\cdot (p-2)\cdots m\cdot (p-m)\equiv -1(\mathrm{mod}p)}$

و:

${\displaystyle 1\cdot (p-1)\cdot 2\cdot (p-2)\cdots m\cdot (p-m)\equiv 1\cdot (-1)\cdot 2\cdot (-2)\cdots m\cdot (-m)\equiv -1(\mathrm{mod}p)}$

در نتیجه:

${\displaystyle \prod _{j=1}^m{j}^2\equiv (-1{)}^{m+1}(\mathrm{mod}p)}$

یا:

${\displaystyle (m!{)}^2\equiv (-1{)}^{m+1}(\mathrm{mod}p)}$

و با استفاده از این رابطۀ آخری می‌توان ثابت کرد که ${\displaystyle (-1)}$

مشارکت‌کنندگان ویکی‌پدیا. «Wilson's theorem». در دانشنامهٔ ویکی‌پدیای انگلیسی.