חבורת אוילר

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

מקובל לסמן את החבורה ב-U_n, \text{Euler}(n) או \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, חזקה של מספר ראשוני אי-זוגי, או פעמיים חזקה כזו (ראו איבר פרימיטיבי).

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

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

## ראו גם
*פונקציית אוילר
*משפט אוילר
*איבר פרימיטיבי

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

קטגוריה:תורת המספרים
קטגוריה:תורת החבורות
קטגוריה:סדרות של מבנים אלגבריים
קטגוריה:לאונרד אוילר
קטגוריה:חשבון מודולרי