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