מבחן אוילר

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

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

נוסח מבחן אוילר: יהי \ p מספר ראשוני אי זוגי ויהי \ a מספר זר ל- \ p , \ a הוא שארית ריבועית של \ p אם ורק אם a^{(p-1)/2}\equiv1\pmod{p}.

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

כיוון ראשון: נניח כי \ a הוא שארית ריבועית של \ p, זאת אומרת, עבור \ x כלשהו x^2\equiv a\pmod{p}. לפי המשפט הקטן של פרמה x^{p-1}\equiv 1\pmod{p}.
. \ x^{p-1}=x^{2(p-1)/2}=(x^2)^{(p-1)/2}=a^{(p-1)/2}. לכן, a^{(p-1)/2}\equiv 1\pmod{p}.

כיוון שני: נניח כי a^{(p-1)/2}\equiv 1\pmod{p}. כיוון ש \ U_p היא חבורה ציקלית, אזי קיים לה יוצר, יהי g \in \mathbb{Z}/p\mathbb{Z} היוצר שלה. מכיוון ש a \in \mathbb{Z}/p\mathbb{Z} אז \ a=g^{\alpha} עבור \ \alpha כלשהו.\ a^{(p-1)/2}=(g^{\alpha})^{(p-1)/2}=g^{\alpha(p-1)/2}=1\pmod{p}. הסדר של \ g הוא \ p-1, לכן \ p-1 מחלק את \ \alpha(p-1)/2 ומכאן ש-\ \alpha/2 מספר שלם, יהי \ \beta=\alpha/2. עבור \ x=g^\beta מתקיים \ x^2=(g^\beta)^2=g^{2\beta}=g^\alpha=a, ולכן \ a הוא שארית ריבועית של \ p.

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