قضیه ویلسون

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

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

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

$\prod _{k=1 \atop \gcd(k,m)=1}^{m}\!\!k\ \equiv {\begin{cases}-1{\pmod {m}}&{\text{if }}m=4,\;p^{\alpha },\;2p^{\alpha }\\\;\;\,1{\pmod {m}}&{\text{otherwise}}\end{cases}}$

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

مثال

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

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

$(7-1)!=1\times 2\times 3\times 4\times 5\times 6=720\equiv -1{\pmod {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{\pmod {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{\pmod {13}}$

اثبات

برهان اول

چون $\;p$ اول است، پس به ازای هر عدد $\;a$که $\;1\;<a\;<p-1$، عدد منحصر به فرد $\;b$وجود دارد که $a\times b\equiv 1{\pmod {p}}$ و در ضمن $a\not =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{\pmod {p}}$

کاربردها

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

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

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

$1\cdot (p-1)\cdot 2\cdot (p-2)\cdots m\cdot (p-m)\ \equiv \ -1{\pmod {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{\pmod {p}}$

در نتیجه:

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

یا:

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

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

منابع

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