סימן לז'נדר

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

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

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

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

עבור כל זוג (p,a) סימן לז'נדר מוגדר על ידי:

  • a מתחלק ב-p ללא שארית
  • a לא מתחלק ב-p וקיים x שלם המקיים (x²≡a (mod p, כלומר a שארית ריבועית של p
  • a לא מתחלק ב-p ולא קיים x שלם המקיים (x²≡a (mod p, כלומר a אינו שארית ריבועית של 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.

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

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

תכונות סימן לז'נדר[עריכת קוד מקור | עריכה]

אם \ p,q ראשוניים אי זוגיים, ו-\ a,b שלמים, אזי:

  1. 
\left(\frac{ab}{p}\right) = \left(\frac{a}{p}\right)\left(\frac{b}{p}\right)
  2. אם מתקיים a \equiv b \pmod{p} אז מתקיים גם: 
\left(\frac{a}{p}\right) = \left(\frac{b}{p}\right)
  3. 
\left(\frac{1}{p}\right) = 1
  4. 
\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. 
\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. 
\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. 
\left(\frac{5}{p}\right)=\begin{cases} 1 & \mbox{ if }p \equiv \pm 1 \pmod5 \\
-1 & \mbox{ if }p \equiv \pm 2 \pmod5  \end{cases}
  8. \ \left(\frac{p}{q}\right)\left(\frac{q}{p}\right)=\left(-1\right)^{\left(\frac{p-1}{2}\right)\left(\frac{q-1}{2}\right)} (משפט ההדדיות הריבועית)

ראו גם[עריכת קוד מקור | עריכה]

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