מתוך ויקיפדיה, האנציקלופדיה החופשית
בתורת המספרים, סימן יעקובי (על שם המתמטיקאי היהודי-גרמני קרל גוסטב יעקב יעקבי) הוא הכללה של סימן לז'נדר.
שימושו העיקרי הוא בפירוק ובדיקת ראשוניות של מספרים שלמים, בעיקר בשביל יישומים שונים בתחום הקריפטוגרפיה.
לסימן יעקובי יש הכללה רחבה יותר הנקראת סימן קרונקר
עבור מספר שלם ומספר טבעי אי־זוגי , סימן יעקובי מוגדר כמכפלת סימני לז'נדר המתאימים לפירוק של לגורמיו הראשוניים:
- כאשר .
עבור כל זוג סימן לז'נדר מוגדר על ידי:
- מתחלק ב־ ללא שארית.
- זר ל־ והוא שארית ריבועית מודולו .
- זר ל־ ואינו שארית ריבועית מודולו .
|
|
התכונות של סימן יעקובי נובעות ישירות מהקשר שלו לסימן לז'נדר.
- אם ראשוני אי־זוגי, סימן יעקובי הוא פשוט סימן לז'נדר.
- אם אזי .
- ולכן (או )
- ולכן (או )
- משפט ההדדיות הריבועית: אם מספרים אי־זוגיים זרים, אזי מתקיים:
בדומה לסימן לז'נדר, אם אזי שארית אי־ריבועית מודולו . אם הוא שארית ריבועית מודולו אזי .
בשונה מסימן לז'נדר, אם אזי לא בהכרח שארית ריבועית מודולו .
ולכן סימן יעקובי אינו מגלה אם 33 הוא שארית ריבועית מודולו 5045.