סימן לז'נדר

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

סימן יעקובי הוא הרחבה של סימן לז'נדר.

הגדרה

תחום הפונקציה $ {\textstyle \left({\frac {a}{p}}\right)} $ הוא קבוצת כל הזוגות הסדורים $ {\textstyle \langle p,a\rangle } $ כאשר $ {\textstyle p} $ ראשוני אי־זוגי ו־$ {\textstyle a} $ שלם, וּטווח הפונקציה הוא $ {\textstyle \{-1,0,1\}} $.

עבור כל זוג $ {\textstyle \langle p,a\rangle } $ סימן לז'נדר מוגדר על ידי:

$ {\textstyle a} $ מתחלק ב־$ {\textstyle p} $ ללא שארית; $ {\textstyle a} $ אינו מתחלק ב־$ {\textstyle p} $ וקיים $ {\textstyle x} $ שלם המקיים $ {\textstyle x^{2}\equiv a{\pmod {p}}} $, כלומר $ {\textstyle a} $ שארית ריבועית של $ {\textstyle p} $; $ {\textstyle a} $ אינו מתחלק ב־$ {\textstyle p} $ ולא קיים $ {\textstyle x} $ שלם המקיים $ {\textstyle x^{2}\equiv a{\pmod {p}}} $, כלומר $ {\textstyle a} $ אינו שארית ריבועית של $ {\textstyle p} $.

$ \left({\frac {a}{p}}\right)=\left\{{\begin{matrix}0&a\equiv 0{\pmod {p}}&\\1&a\not \equiv 0{\pmod {p}};&a\equiv x^{2}{\pmod {p}}\\-1&a\not \equiv 0{\pmod {p}};&a\not \equiv x^{2}{\pmod {p}}\end{matrix}}\right. $

הגדרתו המקורית של לז'נדר הייתה באמצעות הנוסחה המפורשת:

$ {\textstyle \left({\frac {a}{p}}\right)\equiv a^{\frac {p-1}{2}}{\pmod {p}}\;\;{\text{ and }}\left({\frac {a}{p}}\right)\in \{-1,0,1\}} $.

תכונות סימן לז'נדר

יהיו $ {\textstyle p,q} $ ראשוניים אי־זוגיים ו־$ {\textstyle a,b} $ שלמים, אזי:

1. $ {\textstyle \left({\frac {ab}{p}}\right)=\left({\frac {a}{p}}\right)\cdot \left({\frac {b}{p}}\right)} $
2. אם $ {\textstyle a\equiv b{\pmod {p}}} $ אז $ {\textstyle \left({\frac {a}{p}}\right)=\left({\frac {b}{p}}\right)} $
3. $ {\textstyle \left({\frac {1}{p}}\right)=1} $
4. $ {\textstyle \left({\frac {-1}{p}}\right)=(-1)^{\frac {p-1}{2}}={\begin{cases}1&{\mbox{ if }}p\equiv 1{\pmod {4}}\\-1&{\mbox{ if }}p\equiv 3{\pmod {4}}\end{cases}}} $
5. $ {\textstyle \left({\frac {2}{p}}\right)=(-1)^{\frac {p^{2}-1}{8}}={\begin{cases}1&{\mbox{ if }}p\equiv \pm 1{\pmod {8}}\\-1&{\mbox{ if }}p\equiv \pm 3{\pmod {8}}\end{cases}}} $
6. $ {\textstyle \left({\frac {3}{p}}\right)={\begin{cases}1&{\mbox{ if }}p\equiv \pm 1{\pmod {12}}\\-1&{\mbox{ if }}p\equiv \pm 5{\pmod {12}}\end{cases}}} $
7. $ {\textstyle \left({\frac {5}{p}}\right)={\begin{cases}1&{\mbox{ if }}p\equiv \pm 1{\pmod {5}}\\-1&{\mbox{ if }}p\equiv \pm 2{\pmod {5}}\end{cases}}} $
8. $ {\textstyle \left({\frac {p}{q}}\right)\cdot \left({\frac {q}{p}}\right)={(-1)}^{{\frac {p-1}{2}}\cdot {\frac {q-1}{2}}}} $ (משפט ההדדיות הריבועית)

ראו גם

• שארית ריבועית
• סימן יעקובי
• משפט ההדדיות הריבועית
• פולינום פקטה

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

• סימן לז'נדר, באתר MathWorld (באנגלית)

הערך באדיבות ויקיפדיה העברית, קרדיט,
רשימת התורמים
רישיון cc-by-sa 3.0

סימן לז'נדר34176184Q748339