משפט וילסון

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

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

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

היסטוריה

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

הוכחה

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

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

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

יישומים

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

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

המשפט ההפוך

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

הכללה

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

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

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

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

ראו גם

• הלמה של גאוס

קישורים חיצוניים

• משפט וילסון, באתר MathWorld (באנגלית)
• משפט וילסון, באתר אנציקלופדיה בריטניקה (באנגלית)