הלמה של גאוס (תורת המספרים) – הבדלי גרסאות
תוכן שנמחק תוכן שנוסף
{{שכתוב}} |
עריכה |
||
שורה 4:
על אף שהלמה אינה יעילה ככלי חישוב, יש לה חשיבות [[תאוריה|תאורטית]], כטענת עזר בהוכחות רבות של משפט ההדדיות הריבועית.
יהי p מספר ראשוני אי זוגי, ונניח ש-
<math>\ S = '''הוכחה'''. מכיוון ש- a זר ל- p, כל <math>\ (p-1)/2</math> המספרים בקבוצה S שונים זה מזה מודולו p. נסמן ב-
<math>\ r_1,\dots,r_m</math> את שאריות החילוק הקטנות מ- p/2, וב- <math>\ s_1,\dots,s_n</math> את שאריות החילוק הגדולות מ- p/2. המספרים <math>\ r_1,\dots,r_m,p-s_1,\dots,p-s_n</math> כולם חיוביים וקטנים מ- p/2. יתרה מזו, אלו מספרים שונים, מפני שאם
<math>\ p-s_i = r_j</math>, כאשר <math>\ r_i \equiv u a \pmod{p}</math> ו-<math>\ s_j \equiv v a \pmod{p}</math>, אז
<math>\ u+v \equiv 0 \pmod{p}</math>, והרי המכפלות בקבוצה S הן תמיד בגורמים קטנים מ- p/2.
אם כך, המספרים ברשימה הנ"ל שווים למספרים <math>\ 1,2,\dots,(p-1)/2</math> בסדר מתאים, ומכפלתם שווה ל- <math>\ (p-1/2)!</math>; לכן
<math>\ r_1\dots r_m (p-s_1)\dots (p-s_n) = (-1)^n r_1 \dots r_m \cdot s_1 \dots s_n \equiv ((p-1)/2)! \pmod{p}</math>. מצד שני, המספרים <math>\ r_1,\dots,r_m, s_1,\dots,s_n</math> מהווים סידור מחדש של הקבוצה S, ומכאן ש-
<math>\ ((p-1)/2)! \equiv (-1)^n \cdot a^{(p-1)/2} \cdot ((p-1)/2)! \pmod{p}</math>. לכן
<math>\ (-1)^n \equiv a^{(p-1)/2} \pmod{p}</math>. אבל לפי מבחן אוילר,
<math>\ (a/p) = a^{(p-1)/2}</math>.
== ראו גם ==
* [[משפט ההדדיות הריבועית]]
[[קטגוריה:שאריות ריבועיות]]
|