סימן יעקובי

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

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

הגדרה

עבור מספר שלם $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 (באנגלית)