איבר פרימיטיבי

מתוך ויקיפדיה, האנציקלופדיה החופשית
קפיצה אל: ניווט, חיפוש

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

שורש פרימיטיבי מסדר ראשוני[עריכת קוד מקור | עריכה]

כפי שהוכיח גאוס, החבורה \ U_p ציקלית עבור כל p ראשוני. כל יוצר שלה, כלומר איבר מסדר p-1 בה הוא שורש פרימיטיבי. מספר השורשים הפרימיטיביים הוא מספר האיברים הזרים לp-1, כלומר \ \phi(p-1), כאשר \ \phi היא פונקציית אוילר.

לדוגמה, אם p=7 בחבורה {U}_{7}=\{1,2,3,4,5,6\} יש \ \phi(6)=2 שורשים פרימיטיביים, והם: \{3,5\}.

אם כבר מצאנו שורש פרימטיבי אחד, נאמר g, אזי קבוצת כל השורשים הפרימיטיביים היא \{g^a | (a,p-1)=1 \}.

שורשים פרימיטיביים מסדרים אחרים[עריכת קוד מקור | עריכה]

ניתן להכליל את המונח שורש פרימיטיבי לכל חבורת אוילר ציקלית. נאמר שg שורש פרימיטיבי מודולו m אם הסדר שלו בחבורה Z_{m} הוא \ \phi(m).

נסקור את הסדרים שבהם אכן קיים שורש פרימיטיבי.

  • מודולו 4 - זהו מקרה נאיבי שקל לבדוק ישירות, שכן למשל 3 הוא שורש פרימיטיבי. מאידך, אפשר לראות שמודולו 8 כבר אין שורש פרימיטיבי, שכן הסדר של כל האיברים שם הוא 2. זה נכון לכל n כללי, כלומר אין שורש פרימיטיבי ל2^n החל מn\ge3.
  • מודולו p^m לכל a\ge1. נוכיח שאכן קיים לסדר זה שורש פרימיטיבי בשלבים.

ראשית, נוכיח שקיים שורש פרימיטיבי מודולו p^2. ידוע כבר שקיים שורש פרימיטיבי מודולו p, נסמנו g_0.

נשתמש בטענת העזר הבאה - הסדר של g_0 מודולו p, מחלק את הסדר של g_0 מודולו p^2. בנוסף, הסדר של g_0 מודולו p^2 מחלק את הסדר של החבורה, כלומר את p(p-1).

מכאן שהסדר של g_0 מודולו p^2 הוא p-1 או p(p-1). אם הוא p(p-1) סיימנו. נניח שהוא p-1, נביט באיבר (p+1)g_0. הסדר של (p+1) הוא p כי: (p+1)^p=\sum _{ i=0 }^{ p }{ \begin{pmatrix} p \\ i \end{pmatrix}{ p }^{ i }{ 1 }^{ n-i } } =1+\begin{pmatrix} p \\ 1 \end{pmatrix}p+\begin{pmatrix} p \\ 2 \end{pmatrix}{ p }^{ 2 }+...=1+{ p }^{ 2 }+...\equiv 1mod({ p }^{ 2 }) לפי הבינום של ניוטון.

לכן, הסדר של (p+1)g_0 הוא p(p-1), כי (p,p-1)=1.


כעת, נוכיח שקיים שורש פרימיטיבי מודולו חזקת ראשוני.

נעזר בטענת העזר הבאה: לכל m\ge2 מתקיים - אם g^{p-1}\not\equiv 1 mod(p^2) אז g^{p^{m-2}(p-1)}\not\equiv 1mod(p^m).

הוכחת הטענה: באינדוקציה על m. עבור m=2 התוצאה מידית. נניח נכונות לm. מתקיים: g^{\phi(p^{m-1})}=g^{p^{m-2}(p-1)}\equiv 1mod(p^{m-1}), לפי משפט אוילר.

אם כן, קיים C כך ש: g^{p^{m-2}(p-1)}=Cp^{m-1}+1. מתקיים גם p\nmid C, אחרת g^{p^{m-2}(p-1)}\equiv 1mod(p^m) בסתירה לנתון.

מכאן, נעלה בחזקת p את שני האגפים נקבל: g^{p^{m-1}(p-1)}=(Cp^{m-1}+1)^p\equiv Cp^m+1 ,שוב לפי הבינום. היות שp\nmid C קיבלנו g^{p^{m-1}(p-1)} \not\equiv 1mod(p^{m+1}) כדרוש.

הטענה אומרת, שאם g הוא שורש פרימיטיבי מודולו p^2, אז הסדר שלו לא מתחלק על מודולו p^{m-2}(p-1). אבל הסדר הוא מהצורה p^{k}(p-1), לכן k>m-2, כלומר k=m-1, ולכן הסדר מקסימלי, כדרוש.

  • מודולו 2p^m - כבר ראינו שקיים שורש פרימיטיבי מודולו p^m, נניח g. ניקח אותו, ונראה שהוא גם שורש פרימיטיבי מודולו 2p^m. צריך להראות שהסדר שלו הוא \phi(2p^m)=\phi(2)\phi(p^m)=\phi(p^m). נראה זאת:

נסמן את הסדר של g מודולו p^m להיות O_{m}(g), ואת הסדר שלו מודולו 2p^m, להיות O^2_{m}(g). בדומה לטענה שהובאה לעיל, אפשר להראות כי O_{m}(g)|O^2_{m}(g) . זה אומר: \phi(p^m)|O^2_{m}(g)|\phi(2p^m), אבל לפי השוויון לעיל נובע: \phi(2p^m)|O^2_{m}(g)|\phi(2p^m), ולכן הסדר שלו מקסימלי, כדרוש.


בזאת הושלמה הסקירה, שכן גאוס הוכיח שאלו הם הסדרים היחידים להם יש שורשים פרימיטיביים - 1,2,4,p^a,2p^a

לכל n כמו אלו שתוארו לעיל, יש בחבורה \ \phi(n) איברים שמהם \ \phi(\phi(n)) שורשים פרימיטיביים.

גדלים של שורשים פרימיטיביים[עריכת קוד מקור | עריכה]

לאחר הסיווג של הסדרים, עולה השאלה - אם כבר קיים שורש פרימיטיבי, מהו השורש הפרימיטיבי המינימלי? למשל, במקרה הנ"ל עם p=7, הוצג כי שני השורשים הם 3,5 והמינימלי שבהם הוא 3.

מתברר שהתשובה לשאלה זו אינה פשוטה ואינה שלמה. הוכחו בנושא מספר טענות, והועלו השערות כדלהלן:

  • השורש הפרימיטיבי המינימלי g במודולו p מקיים g\le C{ p }^{ \frac { 1 }{ 4 }  } כאשר C קבוע חיובי.
  • קיימים אינסוף ראשוניים כך שהשורש הפרימיטיבי המינימלי g מקיים g\ge Klog(p), כאשר K קבוע חיובי.

שימושים ומסקנות[עריכת קוד מקור | עריכה]

השימוש בשורשים פרימיטיביים הוא רב, ולעתים הם משמשים כלי עזר במקומות בלתי צפויים.

ראשית, מתקיימת הטענה הבאה: אם g שורש פרימיטיבי, אזי a\equiv g^kmod(p) היא שארית ריבועית אם ורק אם k זוגי. בפרט, נובע כי כל שורש פרימטיבי אינו שארית ריבועית (המקרה של k=1).

כלומר, אם מצאנו שורש פרימיטיבי, יש בידינו דרך למצוא את כל השאריות הריבועיות - יש להעלות אותו בכל החזקות הזוגיות הקטנות מp-1, וכך יתקבלו כל השאריות הריבועיות.

ראו גם[עריכת קוד מקור | עריכה]

חבורת אוילר

סדר של איבר