לדלג לתוכן

משפט וילסון

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

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

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

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

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

יהי p ראשוני. לכל 1≤a≤p−1 קיים 1≤b≤p−1 יחיד עבורו ab≡1(modp) (זהו ההפכי של a בחבורת אוילר Up).
אם a הפוך לעצמו אז p∣(a−1)(a+1), ולכן המספרים היחידים ההפוכים לעצמם הם 1,p−1.
מכאן שבמכפלה (p−1)!, כל המספרים פרט ל-1,p−1 ניתנים לסידור בזוגות שמכפלתם מודולו p היא 1, ולכן

(p−1)!=1⋅2⋯(p−1)≡p−1≡−1(modp)

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

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

(p−1)!=1⋅(p−1)⋅2⋅(p−2)⋯p−12⋅(p−p−12)≡1⋅(−1)⋅2⋅(−2)⋯p−12⋅(−p−12)(modp)≡(−1)p−12[(p−12)!]2≡−1(modp)[(p−12)!]2≡(−1)p+12(modp)≡{−1(modp):p≡1(mod4)1(modp):p≡3(mod4)

המשפט ההפוך

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

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

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

∏k=1gcd⁡{k,n}=1nk≡{−1(modn):n=4,pm,2pm1(modn):otherwise

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

המכפלה האחרונה היא למעשה מכפלת האיברים בחבורת אוילר Un. את הטענה ניתן להכליל לכל חבורה אבלית סופית: מכפלת האיברים בחבורה כזו היא תמיד איבר היחידה, אלא אם כן קיים איבר יחיד מסדר 2, ואז המכפלה שווה אליו. גאוס הוכיח שבמקרים n=4,pm,2pm חבורת אוילר היא חבורה ציקלית מסדר זוגי (הזוגיות נובעת מתכונות פונקציית אוילר) ולכן −1 הוא אכן האיבר היחיד בה שסדרו 2.

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

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