חבורת אוילר

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

חבורת אוילר מסדר 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$ ).