חבורת אוילר

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

מקובל לסמן את החבורה ב- $U_{n}$ , ${\text{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$ אזי אלגוריתם אוקלידס המורחב מאפשר למצוא מספרים שלמים $x,y$ עבורם $xa+yn=1$ , ובחישוב מודולו $n$ מתקבל כי $u$ הוא ההופכי של $a$ (הנקרא הופכי כפלי מודולרי של $a$ ); מכאן שהקבוצה כוללת, עבור כל איבר שלה, גם איבר הפכי – ולכן היא חבורה.

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

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

המבנה של חבורת אוילר

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

כך אפשר לפרק את חבורת אוילר באופן כללי. למשל,

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}}\cdots p_{k}^{s_{k}}$ מתקבלת מהכפלת כל המספרים $p_{i}^{s_{i}-1}(p_{i}-1)$ , הפונקציה $\lambda$ שווה לכפולה המשותפת המינימלית של כל המספרים האלה (לאחר שהגורם $2^{s-1}$ מוחלף ב- $2^{s-2}$ , אם $s\geq 2$ ).