משפט וילסון – הבדלי גרסאות

עיון אינטראקטיבי בהיסטוריה

→ העריכה הקודמת העריכה הבאה ←

תוכן שנמחק תוכן שנוסף

חזותיקוד ויקי

בשורה

גרסה מ־18:04, 6 בפברואר 2009

משפט וילסון הוא משפט בתורת המספרים המספק תנאי מספיק והכרחי לראשוניותו של מספר חיובי.

המשפט

יהי

\ m

מספר שלם חיובי.

\ m

ראשוני אם ורק אם

\ m

מחלק את

\ (m-1)!+1

.

ובניסוח שקול:

\ p>1

הוא מספר ראשוני אם ורק אם

(p-1)!\ \equiv \ -1\ ({\mbox{mod}}\ p)

.

(ראו חשבון מודולרי ועצרת לסימונים).

היסטוריה

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

הוכחה

למשפט שני כיוונים, ראשית נוכיח את המשפט "אם מספר $\ m$ מחלק את $\ 1+!(m-1)$ אז $\ m$ ראשוני".

יהי $\ m$ מספר פריק אזי ניתן לכתוב את $\ m$ כמכפלת שני מספרים $\ a,b$ כך ש $a\cdot b=m$ וגם $1\lneq a,b\lneq m$ . לכן $\ a|(m-1)!$ ולכן $\ a$ זר ל- $\ 1+!(m-1)$ ולכן $\ m$ לא מחלק את $\ 1+!(m-1)$ . ולכן, על-ידי היפוך ושלילה נקבל כי אם מספר $\ m$ מחלק את $\ 1+!(m-1)$ אז m אינו פריק ועל כן ראשוני.

כעת לכיוון ההפוך, אם p מספר ראשוני אזי $\ p$ מחלק את $\ 1+!(p-1)$ . ע"מ להוכיח טענה זו נסתמך על מספר משפטים בסיסיים מחשבון מודולרי. $\ p$ ראשוני, לכן לכל מספר $a\neq 0$ קיים הופכי יחיד $\ b$ מודולו $\ p$ כך ש $\ a\cdot b\equiv 1\mod {p}$ (ההפכי הנ"ל על-פי משפט אוילר הוא $\ a^{p-2}$ ). נתבונן במשוואה $\ a\equiv a^{-1}\mod {p}$ נפשט ונקבל $\ a^{2}\equiv 1\mod {p}$ ולכן $\ a^{2}-1\equiv 0\mod {p}$ ואז $\ a\equiv 1\mod {p}$ או $\ a\equiv -1\equiv p-1\mod {p}$ לכן במכפלה של $\ 1\cdot 2\cdot 3...\cdot (p-2)$ לכל איבר מופיע גם ההפכי (היחיד) שלו במכפלה. ולכן, בגלל קומוטטיביות הכפל, $\ 2\cdot 3\cdot ...\cdot (p-2)\equiv 1\mod {p}$ ולכן $\ (p-1)!\equiv p-1\equiv -1\mod {p}$ ולכן $\ (p-1)!+1\equiv 0\mod {p}$ ולכן $\ p$ מחלק את $\ (p-1)!+1$ .

@@ שורה 11: / שורה 11: @@
 (ראו [[חשבון מודולרי]] ו[[עצרת]] ל[[סימן מתמטי|סימונים]]).
-==היסטוריה ==
+== היסטוריה ==
 הראשון שגילה את המשפט היה ככל הנראה המתמטיקאי ה[[הודי]] Bhāskara I, מאוחר יותר המשפט הוסבר על-ידי המדען ה[[ערבי]] [[איבן אל-היית'ם]] ב[[ימי הביניים]], בערך בשנת 1000 לספירה. המשפט קרוי על שמו של [[ג'ון וילסון]], מתמטיקאי אנגלי וסטודנט של [[אדוארד וארינג]], שהזכיר את המשפט במאה ה-18. וארינג הכריז על המשפט ב-1770 למרות שגם הוא וגם וילסון לא יכלו להוכיח אותו. [[ז'וזף לואי לגראנז'|לגראנז']] היה הראשון להוכיח את המשפט בשנת 1773. ישנן ראיות ש[[גוטפריד וילהלם לייבניץ|לייבניץ]] היה מודע לכך כעשור קודם לכן, אך לעולם לא פרסם זאת.
 == הוכחה ==
 למשפט שני כיוונים, ראשית נוכיח את המשפט "אם מספר <math>\ m</math> [[מחלק]] את <math>\ 1+!(m-1)</math> אז <math>\ m</math> ראשוני".
@@ שורה 23: / שורה 25: @@
 כעת לכיוון ההפוך, אם p מספר ראשוני אזי <math>\ p</math> מחלק את <math>\ 1+!(p-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>.
+<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>.
 [[קטגוריה:משפטים מתמטיים]]