מבחן אוילר

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

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

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

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

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

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

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