|
'''משפט וילסון''' הוא [[משפט (מתמטיקה)|משפט]] ב[[תורת המספרים|תורת המספרים]], המספקהקובע [[אםשאם ורקp אם|תנאי מספיק והכרחי]] ל[[מספר ראשוני|ראשוניותו]], שלאז p מחלק את <math>\ (p-1)!+1</math> (ראו [[מספר חיוביעצרת]] למשמעות הסימון "!").
== המשפט ==
:עבור כל <math>\ m</math> [[מספר שלם|שלם]] וגדול מ-1, <math>\ m</math> [[מספר ראשוני|ראשוני]] [[אם ורק אם]] <math>\ m</math> [[מחלק]] את <math>\ (m-1)! + 1</math>.
ובניסוח שקול:
:<math>\ p>1</math> הוא [[מספר ראשוני]] [[אם ורק אם]] <math>(p-1)!\ \equiv\ -1\ (\mbox{mod}\ p)</math>.
(ראו [[חשבון מודולרי]] ו[[עצרת]] ל[[סימן מתמטי|סימונים]]).
== היסטוריה ==
== הוכחה ==
נניח ש- p ראשוני. לכל <math>\ 1\leq a < p</math> קיים b יחיד באותו טווח, המקיים <math>\ ab \equiv 1 \pmod{p}</math> (זהו ההפכי של a ב[[חבורת אוילר]] <math>\ U_p</math>). אם a הפוך לעצמו אז <math>\ p |(a-1)(a+1)</math>, ולכן המספרים היחידים ההפוכים לעצמם הם 1 ו- p-1. מכאן שבמכפלה <nowiki>\ (p-1)! = 1 \cdot 2 \cdot \dots (p-1)</nowiki>, כל המספרים פרט ל- 1 ו- p-1 מסודרים בזוגות שמכפלתם 1, ולכן המכפלה כולה שקולה מודולו p ל- 1-.
למשפט שני כיוונים, ראשית נוכיח את המשפט "אם מספר <math>\ m</math> [[מחלק]] את <math>\ (m-1)! + 1</math> אז <math>\ m</math> ראשוני".
אותה הוכחה מתאימה לתוצאה כללית יותר: מכפלת כל האיברים בחבורה אבלית סופית שווה למכפלת ה[[אינוולוציה (תורת החבורות)|איברים מסדר 2]] בחבורה.
== ראו גם ==
* [[הלמה של גאוס (תורת המספרים)|הלמה של גאוס]]
יהי <math>\ m</math> [[מספר פריק]] אזי ניתן לכתוב את <math>\ m</math> כמכפלת שני מספרים <math>\ a, b</math> כך ש <math>a \cdot b = m</math> וגם <math>1 \lneq a,b \lneq m</math>.
לכן <math>\ a | (m-1)!</math> ולכן <math>\ a</math> [[מספרים זרים|זר]] ל-<math>\ (m-1)! + 1</math> ולכן <math>\ m</math> לא מחלק את <math>\ (m-1)! + 1</math>.
ולכן, על ידי [[היפוך ושלילה]] נקבל כי אם מספר <math>\ m</math> מחלק את <math>\ (m-1)! + 1</math> אז m אינו פריק ועל כן ראשוני.
כעת לכיוון ההפוך, אם <math>\ p</math> מספר ראשוני אזי <math>\ p</math> מחלק את <math>\ (p-1)! + 1</math>.
על מנת להוכיח טענה זו נסתמך על מספר משפטים בסיסיים מ[[חשבון מודולרי]].
<math>\ p</math> ראשוני, לכן לכל מספר <math>a \neq 0</math> קיים [[הופכי כפלי מודולרי|הופכי]] יחיד <math>\ b</math> מודולו <math>\ p</math> כך ש <math>\ a \cdot b \equiv 1\mod{p}</math> (ההפכי הנ"ל על-פי [[משפט אוילר]] הוא <math>\ a^{p-2}</math>). נתבונן במשוואה <math>\ a \equiv a^{-1}\mod{p}</math> נפשט ונקבל <math>\ a^2 \equiv 1\mod{p}</math> ולכן <math>\ a^2-1 \equiv 0\mod{p}</math> ואז <math>\ a \equiv 1\mod{p}</math> או <math>\ a \equiv -1 \equiv p-1 \mod{p}</math> לכן במכפלה של <math>\ 1 \cdot 2 \cdot 3... \cdot (p-2)</math> לכל איבר מופיע גם ההפכי (היחיד) שלו במכפלה. ולכן, בגלל [[קומוטטיביות]] הכפל, <math>\ 2 \cdot 3 \cdot ... \cdot (p-2) \equiv 1\mod{p}</math> ולכן <math>\ (p-1)! \equiv p-1 \equiv -1 \mod{p}</math> ולכן <math>\ (p-1)! +1 \equiv 0 \mod{p}</math> ולכן <math>\ p</math> מחלק את <math>\ (p-1)! +1</math>.
[[קטגוריה:משפטים מתמטיים]]
| 