מבחן אוילר

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

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

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

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

קישורים חיצוניים

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