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

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

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

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

הלמה של גאוס. יהי p מספר ראשוני אי זוגי, ונניח ש- a זר ל- p. אם n הוא מספר המספרים בקבוצה המשאירים שארית גדולה מ- p/2 כשמחלקים אותם ב-p, אז: , כאשר הוא סימן לז'נדר.

הוכחה. מכיוון ש- a זר ל- p, כל המספרים בקבוצה S שונים זה מזה מודולו p. נסמן ב- את שאריות החילוק הקטנות מ- p/2, וב- את שאריות החילוק הגדולות מ- p/2. המספרים כולם חיוביים וקטנים מ- p/2. יתרה מזו, אלו מספרים שונים, מפני שאם , כאשר ו-, אז , והרי המכפלות בקבוצה S הן תמיד בגורמים קטנים מ- p/2.

אם כך, המספרים ברשימה הנ"ל שווים למספרים בסדר מתאים, ומכפלתם שווה ל- ; לכן . מצד שני, המספרים מהווים סידור מחדש של הקבוצה S, ומכאן ש- . לכן . אבל לפי מבחן אוילר, .

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