משפט וילסון

משפט וילסון הוא משפט בתורת המספרים, הקובע שאם $p$ מספר ראשוני אזי הוא מחלק את $(p-1)!+1$ (ראו עצרת למשמעות הסימון "!").

המשפט נקרא על שם ג'ון וילסון, אף על פי שלגראנז' היה הראשון להוכיח את המשפט, בשנת 1773.

הכיוון ההפוך למשפט נכון גם הוא, משום שאם $n\neq 4$ ואינו ראשוני אז הוא מחלק את $(n-1)!$ .

היסטוריה

הראשון שגילה את המשפט היה ככל הנראה המתמטיקאי ההודי Bhāskara I, מאוחר יותר המשפט הוסבר על ידי המדען הערבי איבן אל-היית'ם שחי בתקופת ימי הביניים, בערך בשנת 1000 לספירה. המשפט נקרא על שמו של וילסון, מתמטיקאי אנגלי וסטודנט של אדוארד וארינג, שהזכיר את המשפט במאה ה-18. וארינג הכריז על המשפט בשנת 1770 אף על פי שגם הוא וגם וילסון לא יכלו להוכיח אותו, ולגראנז', ב־1773, היה הראשון שסיפק לו הוכחה. ישנן ראיות שלייבניץ היה מודע לכך כ-90 שנה קודם לכן, אך מעולם לא פרסם זאת.

הוכחה

יהי $p$ ראשוני. לכל $1\leq a\leq p-1$ קיים $1\leq b\leq p-1$ יחיד עבורו $ab\equiv 1\!\!\!{\pmod {p}}$ (זהו ההפכי של $a$ בחבורת אוילר $U_{p}$ ).
אם $a$ הפוך לעצמו אז $p\mid (a-1)(a+1)$ , ולכן המספרים היחידים ההפוכים לעצמם הם $1,p-1$ .
מכאן שבמכפלה $(p-1)!$ , כל המספרים פרט ל- $1,p-1$ ניתנים לסידור בזוגות שמכפלתם מודולו $p$ היא 1, ולכן

(p-1)!=1\cdot 2\cdots (p-1)\equiv p-1\equiv -1\!\!\!{\pmod {p}}

אותה הוכחה מתאימה לתוצאה כללית יותר: מכפלת כל האיברים בחבורה אבלית סופית שווה למכפלת האיברים מסדר 2 בחבורה.

יישומים

אם $p$ ראשוני אי-זוגי, אזי לפי משפט וילסון

{\begin{aligned}(p-1)!&=1\cdot (p-1)\cdot 2\cdot (p-2)\cdots {\frac {p-1}{2}}\cdot \left(p-{\frac {p-1}{2}}\right)\\&\equiv 1\cdot (-1)\cdot 2\cdot (-2)\cdots {\frac {p-1}{2}}\cdot \left(-{\frac {p-1}{2}}\right)\!\!\!{\pmod {p}}\\&\equiv (-1)^{\frac {p-1}{2}}\left[\left({\frac {p-1}{2}}\right)!\right]^{2}\equiv -1\!\!\!{\pmod {p}}\\\left[\left({\frac {p-1}{2}}\right)!\right]^{2}&\equiv (-1)^{\frac {p+1}{2}}\!\!\!{\pmod {p}}\\&\equiv {\begin{cases}-1{\pmod {p}}&:p\equiv 1{\pmod {4}}\\\quad \!1{\pmod {p}}&:p\equiv 3{\pmod {4}}\end{cases}}\end{aligned}}

המשפט ההפוך

נוכיח גרסה חזקה של המשפט ההפוך למשפט וילסון. במקרה $n=4$ מתקיים כי $(4-1)!+1=7$ אינו מתחלק ב-4.
נראה כי אם $n>4$ מספר פריק, אז $n$ מחלק את $(n-1)!$ . נבחר מחלק אמיתי $1<a<n$ . אם $a$ השורש הריבועי של $n$ , אז $a>2$ (כי $n>4$ ), ומכאן $2a<a^{2}=n$ . מאחר ש- $a<2a<n$ הם כלולים במכפלה $(n-1)!$ , ובפרט מכפלה זו מתחלקת במכפלתם $2a^{2}=2n$ , ולכן $n$ מחלק את $(n-1)!$ . אם $a$ אינו שורש של $n$ , אז הוא שונה מ- ${\frac {n}{a}}<n$ , ולכן מכפלתם $n$ מחלקת את $(n-1)!$ .

הכללה

קרל פרידריך גאוס הוכיח את ההכללה הבאה למשפט: לכל $n>2$ מתקיים

\prod _{k\,=\,1 \atop \gcd\{k,n\}=1}^{n}\!\!\!\!k\equiv {\begin{cases}-1{\pmod {n}}&:n=4,p^{m},2p^{m}\\\quad \!1{\pmod {n}}&:{\text{otherwise}}\end{cases}}

כאשר $p$ ראשוני אי-זוגי ו- $m>0$ שלם. משפט וילסון מתקבל כאשר $n$ ראשוני.

המכפלה האחרונה היא למעשה מכפלת האיברים בחבורת אוילר $U_{n}$ . את הטענה ניתן להכליל לכל חבורה אבלית סופית: מכפלת האיברים בחבורה כזו היא תמיד איבר היחידה, אלא אם כן קיים איבר יחיד מסדר 2, ואז המכפלה שווה אליו. גאוס הוכיח שבמקרים $n=4,p^{m},2p^{m}$ חבורת אוילר היא חבורה ציקלית מסדר זוגי (הזוגיות נובעת מתכונות פונקציית אוילר) ולכן $-1$ הוא אכן האיבר היחיד בה שסדרו 2.