סימן יעקובי

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

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

לסימן יעקובי יש הכללה רחבה יותר הנקראת סימן קרונקר

==הגדרה==
עבור מספר שלם <math>a</math> ומספר טבעי אי־זוגי <math>n</math>, סימן יעקובי <math>\left(\frac{a}{n}\right)</math> מוגדר כמכפלת סימני לז'נדר המתאימים לפירוק של <math>n</math> לגורמיו הראשוניים:
:<math>\left(\frac{a}{n}\right)=\left(\frac{a}{p_1}\right)^{\alpha_1}\left(\frac{a}{p_2}\right)^{\alpha_2}\cdots\left(\frac{a}{p_k}\right)^{\alpha_k}</math> כאשר <math>n=p_1^{\alpha_1}p_2^{\alpha_2}\cdots p_k^{\alpha_k}</math>.

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

{| border=0
|-
|
*<math>a</math> מתחלק ב־<math>p</math> ללא שארית.
*<math>a</math> זר ל־<math>p</math> והוא שארית ריבועית מודולו <math>p</math>.
*<math>a</math> זר ל־<math>p</math> ואינו שארית ריבועית מודולו <math>p</math>.
| <math>\left(\frac{a}{p}\right)=\begin{cases}0&:a\equiv0\pmod{p}&\\1&:a\not\equiv0\pmod{p},&a\equiv x^2\pmod{p}\\-1& :a\not\equiv0\pmod{p},&a\not\equiv x^2\pmod{p}\end{cases}</math>
|}

==תכונות==
התכונות של סימן יעקובי נובעות ישירות מהקשר שלו לסימן לז'נדר.
*אם <math>n</math> ראשוני אי־זוגי, סימן יעקובי הוא פשוט סימן לז'נדר.
*אם <math>a\equiv b\!\!\!\pmod{n}</math> אזי <math>\left(\frac{a}{n}\right)=\left(\frac{b}{n}\right)</math>.
*<math>\left(\frac{a}{n}\right)=\begin{cases}0&:\gcd\{a,n\}\ne1\\\pm1&:\gcd\{a,n\}=1\end{cases}</math>
*<math>\left(\frac{ab}{n}\right)=\left(\frac{a}{n}\right)\left(\frac{b}{n}\right)</math> ולכן <math>\left(\frac{a^2}{n}\right)=1</math> (או <math>0</math>)
*<math>\left(\frac{a}{mn}\right)=\left(\frac{a}{m}\right)\left(\frac{a}{n}\right)</math> ולכן <math>\left(\frac{a}{n^2}\right)=1</math> (או <math>0</math>)
*משפט ההדדיות הריבועית: אם <math>m,n</math> מספרים אי־זוגיים זרים, אזי מתקיים:
:<math>\left(\frac{m}{n}\right)\!\left(\frac{n}{m}\right)=(-1)^{\frac{m-1}{2}\frac{n-1}{2}}</math>
*<math>\left(\frac{-1}{n}\right)=(-1)^\frac{n-1}{2}=\begin{cases}1&:p\equiv1\pmod{4}\\-1&:p\equiv3\pmod{4}\end{cases}</math>
*<math>\left(\frac{2}{n}\right)=(-1)^\frac{n^2-1}{8}=\begin{cases}1&:p\equiv\pm1\pmod{8}\\-1&:p\equiv\pm3\pmod{8}\end{cases}</math>
בדומה לסימן לז'נדר, אם <math>\left(\frac{a}{n}\right)=-1</math> אזי <math>a</math> שארית אי־ריבועית מודולו <math>n</math>. אם <math>a</math> הוא שארית ריבועית מודולו <math>n</math> אזי <math>\left(\frac{a}{n}\right)=1</math>.
בשונה מסימן לז'נדר, אם <math>\left(\frac{a}{n}\right)=1</math> אזי <math>a</math> לא בהכרח שארית ריבועית מודולו <math>n</math>.

==דוגמאות==
<math>\begin{align}\left(\frac{33}{5045}\right)=\left(\frac{33}{5\cdot1009}\right)=\left(\frac{33}{5}\right)\left(\frac{33}{1009}\right)\\
\left(\frac{33}{5}\right)=\left(\frac{3\cdot11}{5}\right)=\left(\frac{3}{5}\right)\left(\frac{11}{5}\right)=\left(\frac{5}{3}\right)\cdot(-1)^{\frac{5-1}{2}\frac{3-1}{2}}\left(\frac{1}{5}\right)=\left(\frac{2}{3}\right)\cdot1=-1\\
\left(\frac{33}{1009}\right)=\left(\frac{3}{1009}\right)\left(\frac{11}{1009}\right)\\
\left(\frac{3}{1009}\right)=\left(\frac{1009}{3}\right)\cdot(-1)^\frac{1009-1}{2}=\left(\frac{1009}{3}\right)=\left(\frac{1}{3}\right)=1\\
\left(\frac{11}{1009}\right)=\left(\frac{1009}{11}\right)\cdot(-1)^{\frac{1009-1}{2}\frac{11-1}{2}}=\left(\frac{1009}{11}\right)=\left(\frac{8}{11}\right)=\left(\frac{2}{11}\right)^3=(-1)^3=-1\\
\left(\frac{33}{5045}\right)=\left(\frac{33}{5\cdot1009}\right)=\left(\frac{33}{5}\right)\left(\frac{33}{1009}\right)=(-1)\cdot(-1)=1\end{align}</math>

ולכן סימן יעקובי אינו מגלה אם 33 הוא שארית ריבועית מודולו 5045.

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

קטגוריה:שאריות ריבועיות