חבורת אוילר

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

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

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

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

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

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

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

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

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

כך אפשר לפרק את חבורת אוילר באופן כללי. למשל,
:<math>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</math>
ומכאן שהאקספוננט של חבורה זו הוא <math>16\cdot 5=80</math>. במילים אחרות, לכל a שאינו מתחלק ב-2 או ב-5, מתקיים <math>a^{80} \equiv1\!\!\!\pmod{1600}</math>, והמספר 80 הוא הקטן ביותר בעל תכונה זו.

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

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

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

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