הצגת המקור של הדף "חבורת אוילר"

'''חבורת אוילר''' (נקראת בדרך כלל '''חבורת ההפיכים מודולו <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>).

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

==קישורים חיצוניים==
*{{MathWorld|ModuloMultiplicationGroup}}

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