חבורת אוילר – הבדלי גרסאות
תוכן שנמחק תוכן שנוסף
מ הגהה, עריכת נוסחאות |
מ תיקון, התפספס בעריכה קודמת |
||
שורה 3:
מקובל לסמן את החבורה ב-<math>U_n</math>, <math>Euler(n)</math> או <math>\mathbb{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</math> ו-<math>b</math> שני מספרים הזרים ל-<math>n</math>, אז גם המכפלה <math>ab</math> זרה ל-<math>n</math>. במלים אחרות, הקבוצה <math>U_n</math> סגורה לכפל. בנוסף לזה, אם <math>a</math> זר ל-<math>n</math> אז [[אלגוריתם אוקלידס המוכלל]] מאפשר למצוא מספרים שלמים <math>u,v</math> כך ש-<math>ua+vn=1</math>, ובחישוב מודולו <math>n</math> מתקבל ש-<math>u</math> הוא ההופכי של <math>a</math> (הנקרא [[הופכי כפלי מודולרי]] של <math>a</math>); מכאן שהקבוצה כוללת, עבור כל איבר שלה, גם איבר הפכי - ולכן היא חבורה.
חבורת אוילר מאגדת את התכונות הבסיסיות של החישוב בשאריות מודולו <math>n</math>, ואין פלא שהיא מופיעה תדיר בשימושים של תורת המספרים; לדוגמה, בשיטת ההצפנה [[RSA]].
| |||