סימן יעקובי

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

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

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

הגדרה

עבור מספר שלם $a$ ומספר טבעי אי־זוגי $n$, סימן יעקובי $\left({\frac {a}{n}}\right)$ מוגדר כמכפלת סימני לז'נדר המתאימים לפירוק של $n$ לגורמיו הראשוניים:

$\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}}$ כאשר $n=p_{1}^{\alpha _{1}}p_{2}^{\alpha _{2}}\cdots p_{k}^{\alpha _{k}}$.

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

$a$ מתחלק ב־$p$ ללא שארית. $a$ זר ל־$p$ והוא שארית ריבועית מודולו $p$. $a$ זר ל־$p$ ואינו שארית ריבועית מודולו $p$.

$\left({\frac {a}{p}}\right)={\begin{cases}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{cases}}$

תכונות

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

• אם $n$ ראשוני אי־זוגי, סימן יעקובי הוא פשוט סימן לז'נדר.
• אם $a\equiv b\!\!\!{\pmod {n}}$ אזי $\left({\frac {a}{n}}\right)=\left({\frac {b}{n}}\right)$.
• $\left({\frac {a}{n}}\right)={\begin{cases}0&:\gcd\{a,n\}\neq 1\\\pm 1&:\gcd\{a,n\}=1\end{cases}}$
• $\left({\frac {ab}{n}}\right)=\left({\frac {a}{n}}\right)\left({\frac {b}{n}}\right)$ ולכן $\left({\frac {a^{2}}{n}}\right)=1$ (או $0$)
• $\left({\frac {a}{mn}}\right)=\left({\frac {a}{m}}\right)\left({\frac {a}{n}}\right)$ ולכן $\left({\frac {a}{n^{2}}}\right)=1$ (או $0$)
• משפט ההדדיות הריבועית: אם $m,n$ מספרים אי־זוגיים זרים, אזי מתקיים:

$\left({\frac {m}{n}}\right)\!\left({\frac {n}{m}}\right)=(-1)^{{\frac {m-1}{2}}{\frac {n-1}{2}}}$

• $\left({\frac {-1}{n}}\right)=(-1)^{\frac {n-1}{2}}={\begin{cases}1&:p\equiv 1{\pmod {4}}\\-1&:p\equiv 3{\pmod {4}}\end{cases}}$
• $\left({\frac {2}{n}}\right)=(-1)^{\frac {n^{2}-1}{8}}={\begin{cases}1&:p\equiv \pm 1{\pmod {8}}\\-1&:p\equiv \pm 3{\pmod {8}}\end{cases}}$

בדומה לסימן לז'נדר, אם $\left({\frac {a}{n}}\right)=-1$ אזי $a$ שארית אי־ריבועית מודולו $n$. אם $a$ הוא שארית ריבועית מודולו $n$ אזי $\left({\frac {a}{n}}\right)=1$.
בשונה מסימן לז'נדר, אם $\left({\frac {a}{n}}\right)=1$ אזי $a$ לא בהכרח שארית ריבועית מודולו $n$.

דוגמאות

${\begin{aligned}\left({\frac {33}{5045}}\right)=\left({\frac {33}{5\cdot 1009}}\right)=\left({\frac {33}{5}}\right)\left({\frac {33}{1009}}\right)\\\left({\frac {33}{5}}\right)=\left({\frac {3\cdot 11}{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)\cdot 1=-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\cdot 1009}}\right)=\left({\frac {33}{5}}\right)\left({\frac {33}{1009}}\right)=(-1)\cdot (-1)=1\end{aligned}}$

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

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

• סימן יעקובי, באתר MathWorld (באנגלית)