משפט וילסון

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

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

הכיוון ההפוך למשפט נכון גם הוא, משום שאם <math>n\ne4</math> ואינו ראשוני אז הוא מחלק את <math>(n-1)!</math>.

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

==הוכחה==
יהי <math>p</math> ראשוני. לכל <math>1\le a\le p-1</math> קיים <math>1\le b\le p-1</math> יחיד עבורו <math>ab\equiv1\!\!\!\pmod{p}</math> (זהו ההפכי של <math>a</math> בחבורת אוילר <math>U_p</math>).
אם <math>a</math> הפוך לעצמו אז <math>p\mid(a-1)(a+1)</math>, ולכן המספרים היחידים ההפוכים לעצמם הם <math>1,p-1</math>.
מכאן שבמכפלה <math>(p-1)!</math>, כל המספרים פרט ל-<math>1,p-1</math> ניתנים לסידור בזוגות שמכפלתם מודולו <math>p</math> היא 1, ולכן
:<math>(p-1)!=1\cdot2\cdots(p-1)\equiv p-1\equiv-1\!\!\!\pmod{p}</math>
אותה הוכחה מתאימה לתוצאה כללית יותר: מכפלת כל האיברים בחבורה אבלית סופית שווה למכפלת האיברים מסדר 2 בחבורה.

==יישומים==
אם <math>p</math> ראשוני אי-זוגי, אזי לפי משפט וילסון
:<math>\begin{align}(p-1)!&=1\cdot(p-1)\cdot2\cdot(p-2)\cdots\frac{p-1}{2}\cdot\left(p-\frac{p-1}{2}\right)\\&\equiv1\cdot(-1)\cdot2\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\equiv1\pmod{4}\\\quad\!1\pmod{p}&:p\equiv3\pmod{4}\end{cases}\end{align}</math>

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

==הכללה==
קרל פרידריך גאוס הוכיח את ההכללה הבאה למשפט: לכל <math>n>2</math> מתקיים
:<math>\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}</math>
כאשר <math>p</math> ראשוני אי-זוגי ו-<math>m>0</math> שלם. משפט וילסון מתקבל כאשר <math>n</math> ראשוני.

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

==ראו גם== 
*הלמה של גאוס

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

וילסון
קטגוריה:מספרים ראשוניים
קטגוריה:מבחני ראשוניות
קטגוריה:חשבון מודולרי