סימן לז'נדר

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

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

הגדרה

תחום הפונקציה ${\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}$ שלמים, אזי:

${\textstyle \left({\frac {ab}{p}}\right)=\left({\frac {a}{p}}\right)\cdot \left({\frac {b}{p}}\right)}$
אם ${\textstyle a\equiv b{\pmod {p}}}$ אז ${\textstyle \left({\frac {a}{p}}\right)=\left({\frac {b}{p}}\right)}$
${\textstyle \left({\frac {1}{p}}\right)=1}$
${\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}}}$
${\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}}}$
${\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}}}$
${\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}}}$
${\textstyle \left({\frac {p}{q}}\right)\cdot \left({\frac {q}{p}}\right)={(-1)}^{{\frac {p-1}{2}}\cdot {\frac {q-1}{2}}}}$ (משפט ההדדיות הריבועית)