משפט וילסון

מתוך ויקיפדיה, האנציקלופדיה החופשית
קפיצה אל: ניווט, חיפוש

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

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

היסטוריה[עריכת קוד מקור | עריכה]

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

הוכחה[עריכת קוד מקור | עריכה]

נניח ש־p ראשוני. לכל \ 1\leq a < p קיים b יחיד באותו טווח, המקיים \ ab \equiv 1 \pmod{p} (זהו ההפכי של a בחבורת אוילר \ U_p). אם a הפוך לעצמו אז \ p |(a-1)(a+1), ולכן המספרים היחידים ההפוכים לעצמם הם 1 ו- p-1. מכאן שבמכפלה \ (p-1)! = 1 \cdot 2 \cdot \dots (p-1), כל המספרים פרט ל- 1 ו- p-1 מסודרים בזוגות שמכפלתם מודולו p היא 1, ולכן המכפלה כולה שקולה מודולו p ל־\ -1.

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

יישומים[עריכת קוד מקור | עריכה]

אם p ראשוני אי-זוגי, אז \ (p-1)! = (1\cdot \cdots \cdot \frac{p-1}{2}) \cdot (\frac{p+1}{2} \cdot \cdots \cdot (p-1)) = \left(\frac{p-1}{2}\right)!^2 (-1)^{\frac{p-1}{2}}, ולפי משפט וילסון \ \left(\frac{p-1}{2}\right)!^2 = (-1)^{\frac{p+1}{2}}. לכן, אם \ p\equiv 1 \pmod{4}, הערך \ \left(\frac{p-1}{2}\right)! מהווה שורש ריבועי של 1-. (מאידך, אם \ p\equiv -1 \pmod{4} אז 1- אינו שארית ריבועית).

המשפט ההפוך[עריכת קוד מקור | עריכה]

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

הכללה[עריכת קוד מקור | עריכה]

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


\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}

כש-p הוא ראשוני אי-זוגי, ו-\alpha הוא שלם חיובי. משפט וילסון מתקבל כאשר m ראשוני.

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

ראו גם[עריכת קוד מקור | עריכה]