הצגת המקור של הדף "הלמה של גאוס (תורת המספרים)"

'''הלמה של גאוס''' (על שם ה[[מתמטיקאי]] ה[[גרמנים|גרמני]] [[קרל פרידריך גאוס]]) היא [[למה (מתמטיקה)|למה]] ב[[תורת המספרים]], המספקת תנאי ל[[מספר טבעי]] להיות [[שארית ריבועית]]. 

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

==למה==
יהי <math>p</math> [[מספר ראשוני]] [[זוגיות (מתמטיקה)|אי-זוגי]], ויהי <math>a</math> [[מספרים זרים|מספר זר]] ל-<math>p</math>.

אם <math>n</math> מספר המספרים בקבוצה <math>S=\left\{a,2a,\ldots,\frac{p-1}{2}a\right\}</math> בעלי שארית גדולה מ-<math>\frac{p}{2}</math> בחלוקה ל-<math>p</math>, אזי <math>\left(\frac{a}{p}\right)=(-1)^n</math>, כאשר אגף שמאל הוא [[סימן לז'נדר]]. 

==הוכחה==
<math>a</math> זר ל-<math>p</math>, ולכן כל <math>\frac{p-1}{2}</math> המספרים בקבוצה <math>S</math> שונים זה מזה מודולו <math>p</math>.{{ש}}
תהיינה <math>r_1,\ldots,r_m</math> שאריות החילוק הקטנות מ-<math>\frac{p}{2}</math>, ותהיינה <math>s_1,\ldots,s_n</math> שאריות החילוק הגדולות מ-<math>\frac{p}{2}</math>.{{ש}}
המספרים <math>r_1,\ldots,r_m,p-s_1,\ldots,p-s_n</math> כולם חיוביים וקטנים מ-<math>\frac{p}{2}</math>. יתרה מזו, אלה מספרים שונים מודולו <math>p</math>:{{ש}}
נניח בשלילה כי <math>r_i=p-s_j</math>. אזי קיימים <math>1\le k_1\ne k_2\le\frac{p-1}{2}</math> עבורם
:<math>\begin{align}&k_1a\equiv r_i\!\!\!\!\pmod{p}\\&k_2a\equiv s_j\!\!\!\!\pmod{p}\\&k_1a+k_2a\equiv r_i+s_j=p\equiv0\!\!\!\!\pmod{p}\\&(k_1+k_2)a\equiv0\!\!\!\!\pmod{p}\\&k_1+k_2\equiv0\!\!\!\!\pmod{p}\end{align}</math>
אך <math>1<k_1+k_2<p-1</math>. סתירה.

המספרים <math>r_1,\ldots,r_m,s_1,\ldots,s_n</math> שקולים כמובן לאיברים <math>a,2a,\ldots,\frac{p-1}{2}a</math> בסדר כלשהו.{{ש}}
המספרים <math>r_1,\ldots,r_m,p-s_1,\ldots,p-s_n</math> שווים לאיברים <math>1,2,\ldots,\frac{p-1}{2}</math> בסדר כלשהו. מתקיים{{ש}}
:<math>\begin{align}r_1\cdots r_m\cdot(p-s_1)\cdots(p-s_n)=\left(\frac{p-1}{2}\right)!\equiv r_1\cdots r_m\cdot(-s_1)\cdots (-s_n)\!\!\pmod{p}\\\left(\frac{p-1}{2}\right)!\equiv(-1)^na^{(p-1)/2}\left(\frac{p-1}{2}\right)!\!\!\pmod{p}\\a^{(p-1)/2}\equiv(-1)^n\!\!\!\pmod{p}\end{align}</math>
אך לפי [[מבחן אוילר]] <math>\left(\frac{a}{p}\right)\equiv a^{(p-1)/2}\!\!\!\pmod{p}</math>.

==ראו גם==
*[[משפט ההדדיות הריבועית]]

[[קטגוריה:שאריות ריבועיות]]
[[קטגוריה:משפטים בתורת המספרים|גאוס]]
[[קטגוריה:קרל פרידריך גאוס]]
[[קטגוריה:חשבון מודולרי]]