חבורת אוילר
חבורת אוילר (נקראת בדרך כלל חבורת ההפיכים מודולו $ 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 $).
ראו גם
קישורים חיצוניים
- חבורת אוילר, באתר MathWorld (באנגלית)
חבורת אוילר38762260