הלמה של גאוס (תורת המספרים)

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

הלמה של גאוס היא למה בתורת המספרים, המספקת תנאי למספר טבעי להיות שארית ריבועית. הלמה נקראת על שם קרל פרידריך גאוס שהוכיח אותה לראשונה בדרכו להוכחת משפט ההדדיות הריבועית.

על אף שהלמה אינה יעילה ככלי חישוב, יש לה חשיבות תאורטית, כטענת עזר בהוכחות רבות של משפט ההדדיות הריבועית.

הלמה של גאוס. יהי p מספר ראשוני אי זוגי, ונניח ש- a זר ל- p. אם n הוא מספר המספרים בקבוצה \ S = \{a,2a,3a,\dots,\frac{p-1}{2} a\} המשאירים שארית גדולה מ- p/2 כשמחלקים אותם ב-p, אז: \ \left(\frac{a}{p}\right) = (-1)^n, כאשר (\tfrac {\cdot}{\cdot}) הוא סימן לז'נדר.

הוכחה. מכיוון ש- a זר ל- p, כל \ (p-1)/2 המספרים בקבוצה S שונים זה מזה מודולו p. נסמן ב- \ r_1,\dots,r_m את שאריות החילוק הקטנות מ- p/2, וב- \ s_1,\dots,s_n את שאריות החילוק הגדולות מ- p/2. המספרים \ r_1,\dots,r_m,p-s_1,\dots,p-s_n כולם חיוביים וקטנים מ- p/2. יתרה מזו, אלו מספרים שונים, מפני שאם \ p-s_i = r_j, כאשר \ r_j \equiv u a \pmod{p} ו-\ s_i \equiv v a \pmod{p}, אז \ u+v \equiv 0 \pmod{p}, והרי המכפלות בקבוצה S הן תמיד בגורמים קטנים מ- p/2.

אם כך, המספרים ברשימה הנ"ל שווים למספרים \ 1,2,\dots,(p-1)/2 בסדר מתאים, ומכפלתם שווה ל- \ (p-1/2)!; לכן \ 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}. מצד שני, המספרים \ r_1,\dots,r_m, s_1,\dots,s_n מהווים סידור מחדש של הקבוצה S, ומכאן ש- \ ((p-1)/2)! \equiv (-1)^n \cdot a^{(p-1)/2} \cdot ((p-1)/2)! \pmod{p}. לכן \ (-1)^n \equiv a^{(p-1)/2} \pmod{p}. אבל לפי מבחן אוילר, \ \left(\frac{a}{p}\right) = a^{(p-1)/2}.

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