قضیه ویلسون

قضیۀ ویلسون الگو:انگلیسی قضیه‌ای در نظریۀ اعداد است که توسط ریاضی‌دان انگلیسی جان ویلسون مطرح شده‌است. این قضیه بیان می‌کند که به ازای هر عدد اول مانند $p$داریم: $(p-1)!\stackrel{p}{\equiv }-1$.

تعمیم قضیۀ ویلسون

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

$\prod _{\genfrac{}{}{0ex}{}{k=1}{\gcd (k,m)=1}}^{m}k\equiv \{\begin{array}{cc}-1(\mathrm{mod}m)& \text{if }m=4,p^{\alpha },2p^{\alpha }\\ 1(\mathrm{mod}m)& \text{otherwise}\end{array}$

در اینجا $\alpha$ عددی صحیح و مثبت است.

مثال

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

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

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

$(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)$

$(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)$

اثبات

برهان اول

چون $p$ اول است، پس به ازای هر عدد $a$که $1<a<p-1$، عدد منحصر به فرد $b$وجود دارد که $a\times b\equiv 1(\mathrm{mod}p)$ و در ضمن $a=b$ و $1<b<p-1$. پس می‌توان اعداد $2,3,...,p-2$ را به زوج‌هایی افراز کرد که حاصل‌ضرب دو عدد هر زوج (جفت) به پیمانۀ $p$برابر با $1$شود. پس

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

کاربردها

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

در عمل این الگوریتم برای تعیین اول بودن عدد ناکارآمد است؛ زیرا محاسبه $(n-1)!modb$ برای $n$-های بزرگ، پیچیدگی محاسباتی دارد و الگوریتم‌های سریع‌تری (مثل آزمون تقسیم) برای این کار وجود دارد.

با اعمال قضیۀ ویلسون بر تمام اعداد اول فرد $p=2m+1$ و مرتب کردن اعداد رابطۀ $1\cdot 2\cdots (p-1)\equiv -1(\mathrm{mod}p)$، به رابطۀ زیر می‌رسیم.

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

و:

$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)$

در نتیجه:

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

یا:

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

و با استفاده از این رابطۀ آخری می‌توان ثابت کرد که $(-1)$ برای هر عدد اول فیثاغورسی (به عبارتی اعداد اولی که $p\stackrel{4}{\equiv }1$ باشند) باقی‌ماندۀ درجۀ دو quadratic residue به پیمانۀ $p$ است (یعنی$p^2\stackrel{n}{\equiv }-1$). فرض کنید $p=4k+1$ است. $m$ را برابر $2k$ می‌گیریم، سپس با با توجه به رابطۀ ذکر شده نتیجه می‌گیریم که $(m!{)}^2$ به پیمانۀ $p$ هم‌نهشت با 1- است.