חבורת אוילר

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

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

לדוגמה, חבורת אוילר מסדר 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{\mathbb{Z}}/n\mathbb{\mathbb{Z}}$. אם המספרים n ו- m זרים זה לזה, אפשר להוכיח באמצעות משפט השאריות הסיני, בין אם באופן ישיר ובין אם בעזרת הזהות $\mathbb{\mathbb{Z}}/mn\mathbb{\mathbb{Z}}\cong \mathbb{\mathbb{Z}}/n\mathbb{\mathbb{Z}}\times \mathbb{\mathbb{Z}}/m\mathbb{\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=\varphi (d)$.

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

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

כך אפשר לפרק את חבורת אוילר באופן כללי. למשל, $U_{1600}\cong U_{64}\times U_{25}\cong \mathbb{\mathbb{Z}}/2\mathbb{\mathbb{Z}}\times \mathbb{\mathbb{Z}}/16\mathbb{\mathbb{Z}}\times \mathbb{\mathbb{Z}}/20\mathbb{\mathbb{Z}}\cong \mathbb{\mathbb{Z}}/2\mathbb{\mathbb{Z}}\times \mathbb{\mathbb{Z}}/4\mathbb{\mathbb{Z}}\times \mathbb{\mathbb{Z}}/16\mathbb{\mathbb{Z}}\times \mathbb{\mathbb{Z}}/5\mathbb{\mathbb{Z}}$, ומכאן שהאקספוננט של חבורה זו הוא $16\cdot 5=80$. במלים אחרות, לכל a שאינו מתחלק ב-2 או ב-5, מתקיים $a^{80}\equiv 1(\mathrm{mod}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\le s$).

ראו גם

• פונקציית אוילר
• משפט אוילר
• איבר פרימיטיבי

קישורים חיצוניים

• חבורת אוילר, באתר MathWorld (באנגלית)