מבחן אוילר

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

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

יהי p מספר ראשוני אי-זוגי ויהי a מספר זר ל-p. אזי a הוא שארית ריבועית מודולו p אם ורק אם a(p1)/21(modp).

הוכחה

כיוון ראשון: נניח כי a שארית ריבועית מודולו p, כלומר קיים x עבורו x2a(modp).
לפי המשפט הקטן של פרמה xp11(modp) לכל x הזר ל-p. לכן מתקיים xp1=(x2)(p1)/2a(p1)/21(modp).

כיוון שני: נניח כי a(p1)/21(modp). לכל p ראשוני קיים שורש פרימיטיבי, כלומר איבר מסדר ϕ(p)=p1 אשר חזקותיו שקולות מודולו p לאיברים 1,2,,p1 בסדר כלשהו.
לכן קיים שורש פרימיטיבי r המקיים rka(modp) עבור 1kϕ(p) כלשהו. מתקיים (rk)(p1)/2=rk(p1)/2a(p1)/21(modp).
הסדר ϕ(p) מחלק את kp12 ולכן b=k2 מספר שלם. מתקיים (rb)2=r2b=rka(modp) ולכן a שארית ריבועית מודולו p.

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

ערך זה הוא קצרמר בנושא מתמטיקה. אתם מוזמנים לתרום למכלול ולהרחיב אותו.
הערך באדיבות ויקיפדיה העברית, קרדיט,
רשימת התורמים
רישיון cc-by-sa 3.0

מבחן אוילר39598651Q2346904