قضیه ویلسون

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

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

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

${\displaystyle \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}}}$

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

مثال

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

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

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

اثبات

برهان اول

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

${\displaystyle \;(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}}}$

کاربرد ها

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

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

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

به رابطه ی زیر می رسیم

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

در نتیجه

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

یا

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

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

منابع

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