מבחן אוילר

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

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

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

הוכחה[עריכת קוד מקור | עריכה]

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

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

קישורים חיצוניים[עריכת קוד מקור | עריכה]

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