חבורת אוילר

מתוך ויקיפדיה, האנציקלופדיה החופשית

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

מקובל לסמן את החבורה ב-, או (הסימון האחרון מדגיש כי זוהי חבורת ההפיכים בחוג ). בחבורת אוילר של יש איברים, כאשר היא פונקציית אוילר. מנקודת מבט זו, משפט אוילר הוא משפט לגראנז' המיושם לחבורת אוילר.

לדוגמה, חבורת אוילר מסדר 15 כוללת את המספרים . קיומה של החבורה מבוסס על עובדה שהייתה ידועה כבר לאוקלידס ומופיעה בספרו "יסודות": אם שני מספרים הזרים ל-, אזי גם המכפלה זרה ל-. במילים אחרות, הקבוצה סגורה לכפל. בנוסף לזה, אם זר ל- אזי אלגוריתם אוקלידס המורחב מאפשר למצוא מספרים שלמים עבורם , ובחישוב מודולו מתקבל כי הוא ההופכי של (הנקרא הופכי כפלי מודולרי של ); מכאן שהקבוצה כוללת, עבור כל איבר שלה, גם איבר הפכי – ולכן היא חבורה.

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

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

המבנה של חבורת אוילר[עריכת קוד מקור | עריכה]

על-פי ההגדרה, חבורת אוילר היא חבורת האיברים ההפיכים של החוג . אם המספרים זרים זה לזה, אפשר להוכיח באמצעות משפט השאריות הסיני, בין אם באופן ישיר ובין אם בעזרת הזהות , את האיזומורפיזם . מכאן יוצא שכדי לתאר את חבורת אוילר כמכפלה של חבורות ציקליות, די לתאר חבורה זו עבור שהוא חזקת ראשוני.

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

כדי לראות שחבורת אוילר ציקלית גם עבור חזקות , די להצביע על איבר מסדר (מכפלתו של איבר כזה באיבר מסדר היא מסדר ). ואכן, כאשר אי-זוגי, האיבר הוא כזה. לדוגמה, בחבורה , האיבר 2057 הוא מסדר 4, ואילו 6 מסדר 625. המכפלה, 2967, יוצרת את החבורה.

במקרה של חזקת 2 החבורה אינה ציקלית, ובמקום זה (כאשר ). את החבורה יוצרים המספרים .

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

ומכאן שהאקספוננט של חבורה זו הוא . במילים אחרות, לכל a שאינו מתחלק ב-2 או ב-5, מתקיים , והמספר 80 הוא הקטן ביותר בעל תכונה זו.

את האקספוננט של חבורת אוילר מסדר מסמנים ב-, בעוד שפונקציית אוילר של מתקבלת מהכפלת כל המספרים , הפונקציה שווה לכפולה המשותפת המינימלית של כל המספרים האלה (לאחר שהגורם מוחלף ב-, אם ).

ראו גם[עריכת קוד מקור | עריכה]

קישורים חיצוניים[עריכת קוד מקור | עריכה]