בתורת השדות הסופיים ויישומיה, איבר פרימיטיבי הוא איבר של שדה סופי, היוצר את החבורה הכפלית של השדה. הפולינום המינימלי של איבר כזה נקרא פולינום פרימיטיבי (אף על פי שלמושג זה יש גם משמעויות אחרות).
גאוס הגדיר את המונח שורשים פרימיטיביים במאמר 57 של ספרו מחקרים אריתמטיים (Disquisitions Arithmeticae), שם הוא נותן את הקרדיט לאוילר על טביעת המונח. במאמר 56 הוא קבע שאוילר ולמברט ידעו עליהם, אך הוא היה הראשון להוכיח ריגורוזית ששורשים פרימיטיביים קיימים. למעשה, מחקרים אריתמטיים כולל שתי הוכחות, האחת במאמר 54 היא הוכחת קיום לא קונסטרוקטיבית, בעוד האחרת ממאמר 55 היא קונסטרוקטיבית.
כפי שהוכיח גאוס, החבורה
ציקלית עבור כל
ראשוני. כל יוצר שלה, כלומר איבר מסדר
בה הוא שורש פרימיטיבי. מספר השורשים הפרימיטיביים הוא מספר האיברים הזרים ל
, כלומר
, כאשר
היא פונקציית אוילר.
לדוגמה, אם
בחבורה
יש
שורשים פרימיטיביים, והם:
.
אם g שורש פרימיטיבי, אז קבוצת כל השורשים הפרימיטיביים היא
.
ניתן להכליל את המונח שורש פרימיטיבי לכל חבורת אוילר ציקלית. נאמר ש-
שורש פרימיטיבי מודולו
אם הסדר שלו בחבורה
הוא
.
נסקור את הסדרים שבהם אכן קיים שורש פרימיטיבי.
- מודולו 4 - זהו מקרה נאיבי שקל לבדוק ישירות, שכן למשל 3 הוא שורש פרימיטיבי. מאידך, אפשר לראות שמודולו 8 כבר אין שורש פרימיטיבי, שכן הסדר של כל האיברים שם הוא 2. זה נכון לכל
כללי, כלומר אין שורש פרימיטיבי ל
החל מ
.
- מודולו
לכל
. נוכיח שאכן קיים לסדר זה שורש פרימיטיבי בשלבים.
ראשית, נוכיח שקיים שורש פרימיטיבי מודולו
. ידוע כבר שקיים שורש פרימיטיבי מודולו
, נסמנו
.
נשתמש בטענת העזר הבאה - הסדר של
מודולו
, מחלק את הסדר של
מודולו
. בנוסף, הסדר של
מודולו
מחלק את הסדר של החבורה, כלומר את
.
מכאן שהסדר של
מודולו
הוא
או
. אם הוא
סיימנו. נניח שהוא
, נביט באיבר
. הסדר של
הוא p כי:
לפי הבינום של ניוטון.
לכן, הסדר של
הוא
, כי
.
כעת, נוכיח שקיים שורש פרימיטיבי מודולו חזקת ראשוני.
נעזר בטענת העזר הבאה: לכל
מתקיים - אם
אז
.
הוכחת הטענה: באינדוקציה על m. עבור
התוצאה מידית. נניח נכונות ל-
. מתקיים:
, לפי משפט אוילר.
אם כן, קיים
כך ש:
. מתקיים גם
, אחרת
בסתירה לנתון.
מכאן, נעלה בחזקת
את שני האגפים נקבל:
,שוב לפי הבינום. היות ש
קיבלנו
כדרוש.
הטענה אומרת, שאם
הוא שורש פרימיטיבי מודולו
, אז הסדר שלו לא מתחלק על מודולו
. אבל הסדר הוא מהצורה
, לכן
, כלומר
, ולכן הסדר מקסימלי, כדרוש.
- מודולו
- כבר ראינו שקיים שורש פרימיטיבי מודולו
, נניח
(אפשר להניח ש-
אי-זוגי; אחרת נחליף אותו ב-
). נראה שהוא גם שורש פרימיטיבי מודולו
. צריך להראות שהסדר שלו הוא
. נראה זאת:
נסמן את הסדר של g מודולו
להיות
, ואת הסדר שלו מודולו
, להיות
. בדומה לטענה שהובאה לעיל, אפשר להראות כי
. זה אומר:
, אבל לפי השוויון לעיל נובע:
, ולכן הסדר שלו מקסימלי, כדרוש.
בזאת הושלמה הסקירה, שכן גאוס הוכיח שאלו הם הסדרים היחידים להם יש שורשים פרימיטיביים - ![{\displaystyle 1,2,4,p^{a},2p^{a}}](//wikimedia.org/api/rest_v1/media/math/render/svg/ca46e40f7acf91a763170cda2a969868f4647cbd)
לכל n כמו אלו שתוארו לעיל, יש בחבורה
איברים שמהם
שורשים פרימיטיביים.
לאחר הסיווג של הסדרים, עולה השאלה - אם כבר קיים שורש פרימיטיבי, מהו השורש הפרימיטיבי המינימלי?
למשל, במקרה הנ"ל עם p=7, הוצג כי שני השורשים הם 3,5 והמינימלי שבהם הוא 3.
מתברר שהתשובה לשאלה זו אינה פשוטה ואינה שלמה. הוכחו בנושא מספר טענות, והועלו השערות כדלהלן:
- השורש הפרימיטיבי המינימלי
במודולו p מקיים
כאשר C קבוע חיובי.
- קיימים אינסוף ראשוניים כך שהשורש הפרימיטיבי המינימלי g מקיים
, כאשר K קבוע חיובי.
- המתמטיקאי אמיל ארטין העלה סברה, לפיה כל מספר שאינו 1- או מספר ריבועי הוא שורש פרימיטיבי של אינסוף ראשוניים.
אפשר להגדיר איבר פרימיטיבי ביחס לכל מספר טבעי n, בתור איבר בעל סדר מקסימלי בחבורת אוילר של n. אם n ראשוני, מתקבלת ההגדרה הקודמת.[1]
השימוש בשורשים פרימיטיביים הוא רב, ולעיתים הם משמשים כלי עזר במקומות בלתי צפויים.
- בפרוטוקולי הצפנה שונים, כדוגמת פרוטוקול דיפי-הלמן, יש שימוש בשורש פרימיטיבי מודולו p ראשוני, המשמש כמפתח ציבורי בפרוטוקול. אם כן, מציאת שורשים פרימיטיביים, במיוחד לראשוניים גדולים מאוד, וסיווג תכונותיהם (כמו גודלם) מקבלת משמעות גם בעולם ההצפנה.
- בעזרת שורשים פרימיטיביים ניתן לסווג את השאריות הריבועיות ב
.
ראשית, מתקיימת הטענה הבאה: אם g שורש פרימיטיבי, אזי
היא שארית ריבועית אם ורק אם k זוגי. בפרט, נובע כי כל שורש פרימיטיבי אינו שארית ריבועית (המקרה של k=1).
כלומר, אם מצאנו שורש פרימיטיבי, יש בידינו דרך למצוא את כל השאריות הריבועיות - יש להעלות אותו בכל החזקות הזוגיות הקטנות מp-1, וכך יתקבלו כל השאריות הריבועיות.
על השערת ארטין במקרה זה, ראו ראו PRIMITIVE ROOTS: A SURVEY, Shuguang Li and Carl Pomerance, “New Aspects of Analytic Number Theory” (RIMS Kokyuroku No. 1274), 2002.