מבחן אוילר

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

נוסח מבחן אוילר: יהי מספר ראשוני אי זוגי ויהי מספר זר ל- , הוא שארית ריבועית של אם ורק אם .

הוכחהעריכה

כיוון ראשון: נניח כי   הוא שארית ריבועית של  , זאת אומרת, עבור   כלשהו  . לפי המשפט הקטן של פרמה  .
.  . לכן,  .

כיוון שני: נניח כי  . כיוון ש   היא חבורה ציקלית, אזי קיים לה יוצר, יהי   היוצר שלה. מכיוון ש   אז   עבור   כלשהו. . הסדר של   הוא  , לכן   מחלק את   ומכאן ש-  מספר שלם, יהי  . עבור   מתקיים  , ולכן   הוא שארית ריבועית של  .

קישורים חיצונייםעריכה

  ערך זה הוא קצרמר בנושא מתמטיקה. אתם מוזמנים לתרום לוויקיפדיה ולהרחיב אותו.