חבורת אוילר

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

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

חבורת אוילר מסדר n כוללת, על-פי ההגדרה, את המספרים השלמים מתוך \{ 1,2,\dots,n\} שהם זרים ל- n, עם פעולת הכפל מודולו n. מקובל לסמן חבורה זו \ U_n, \ Euler(n) או \mathbb{Z}_n^\times (הסימון האחרון מדגיש כי זוהי חבורת ההפיכים בחוג \mathbb{Z}_n). השימוש במלה "סדר" בהקשר זה, למרות שהוא מקובל, עשוי להטעות: בחבורת אוילר מסדר n יש \ \phi(n) אברים, כאשר \ \phi היא פונקציית אוילר. מנקודת מבט זו, משפט אוילר הוא משפט לגראנז' המיושם לחבורת אוילר.

לדוגמה, חבורת אוילר מסדר 15 כוללת את המספרים \ U_{15}=\{1,2,4,7,8,11,13,14\}. קיומה של החבורה מבוסס על עובדה שהייתה ידועה כבר לאוקלידס ומופיעה בספרו "יסודות": אם a ו- b שני מספרים הזרים ל- n, אז גם המכפלה ab זרה ל- n. במלים אחרות, הקבוצה \ U_n סגורה לכפל. בנוסף לזה, אם a זר ל- n אז אלגוריתם אוקלידס המוכלל מאפשר למצוא מספרים שלמים \ u,v כך ש- \ ua+vn=1, ובחישוב מודולו n מתקבל ש- u הוא ההופכי של a (הנקרא הופכי כפלי מודולרי של a); מכאן שהקבוצה כוללת, עבור כל איבר שלה, גם איבר הפכי - ולכן היא חבורה.

חבורת אוילר מאגדת את התכונות הבסיסיות של החישוב בשאריות מודולו n, ואין פלא שהיא מופיעה תדיר בשימושים של תורת המספרים; לדוגמה, בשיטת ההצפנה RSA.

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

המבנה של חבורת אוילר[עריכת קוד מקור | עריכה]

על-פי ההגדרה, חבורת אוילר היא חבורת האיברים ההפיכים של החוג \ \mathbb{Z}/n\mathbb{Z}. אם המספרים n ו- m זרים זה לזה, אפשר להוכיח באמצעות משפט השאריות הסיני, בין אם באופן ישיר ובין אם בעזרת הזהות \ \mathbb{Z}/mn\mathbb{Z} \cong \mathbb{Z}/n\mathbb{Z} \times \mathbb{Z}/m\mathbb{Z}, את האיזומורפיזם \ U_{nm} \cong U_n \times U_m. מכאן יוצא שכדי לתאר את חבורת אוילר כמכפלה של חבורות ציקליות, די לתאר חבורה זו עבור n שהוא חזקת ראשוני.

כאשר p ראשוני, חבורת אוילר \ U_p היא ציקלית. לדוגמה, החבורה \ U_{13} נוצרת על ידי 2. לעובדה שתמיד קיימים יוצרים קטנים יחסית של החבורה יש חשיבות רבה במבחני ראשוניות. טענה זו, על הציקליות של \ U_p, היא מקרה פרטי של משפט כללי יותר - תת-חבורה כפלית, סופית, של שדה היא תמיד ציקלית. כדי להוכיח את הטענה, יש להבחין כי למשוואה \ x^d=1 יש (בשדה) לכל היותר d פתרונות; מצד שני, אם d מחלק את p-1, אז הפולינום \ x^{d}-1 מחלק את הפולינום \ x^{p-1}-1, וכך אפשר לראות שלמשוואה יש בדיוק d פתרונות. אם \ r_d יסמן את מספרם של המספרים שסדרם שווה ל- d, אפשר להוכיח באינדוקציה על d את השוויון \ r_d=\phi(d).

כדי לראות שחבורת אוילר ציקלית גם עבור חזקות \ p^t, די להצביע על איבר מסדר \ p^{t-1} (מכפלתו של איבר כזה באיבר מסדר p-1 היא מסדר \ \phi(p^t)=(p-1)p^{t-1}). ואכן, כאשר p אי-זוגי, האיבר p+1 הוא כזה. לדוגמה, בחבורה \ U_{3125}, לאיבר 2057 יש סדר 4, ואילו ל- 6 יש סדר 625. המכפלה, 2967, יוצרת את החבורה.

במקרה של חזקת 2 החבורה אינה ציקלית, ובמקום זה \ U_{2^t} \cong \mathbb{Z}/2\mathbb{Z}\times \mathbb{Z}/2^{t-2}\mathbb{Z} (כאשר \ t\geq 3). את החבורה יוצרים המספרים \ U_{2^t}=<-1,5>.

כך אפשר לפרק את חבורת אוילר באופן כללי. למשל, \ U_{1600}\cong U_{64}\times U_{25} \cong \mathbb{Z}/2\mathbb{Z} \times \mathbb{Z}/16\mathbb{Z} \times \mathbb{Z}/20\mathbb{Z} \cong \mathbb{Z}/2\mathbb{Z} \times \mathbb{Z}/4\mathbb{Z} \times \mathbb{Z}/16\mathbb{Z} \times \mathbb{Z}/5\mathbb{Z}, ומכאן שהאקספוננט של חבורה זו הוא \ 16\cdot 5=80. במלים אחרות, לכל a שאינו מתחלק ב- 2 או ב- 5, מתקיים \ a^{80} \equiv 1\pmod{1600}, והמספר 80 הוא הקטן ביותר בעל תכונה זו.

את האקספוננט של חבורת אוילר מסדר n מסמנים ב-\ \lambda(n), בעוד שפונקציית אוילר של \ n = p_1^{s_1}\dots p_k^{s_k} מתקבלת מהכפלת כל המספרים \ p_i^{s_i-1}(p_i-1), הפונקציה \ \lambda שווה לכפולה המשותפת המינימלית של כל המספרים האלה (לאחר שהגורם \ 2^{s-1} מוחלף ב-\ 2^{s-2}, אם \ 2 \leq s).

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

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