חבורת אוילר – הבדלי גרסאות

תוכן שנמחק תוכן שנוסף
Matanyabot (שיחה | תרומות)
שורה 7:
חבורת אוילר מאגדת את התכונות הבסיסיות של החישוב בשאריות מודולו n, ואין פלא שהיא מופיעה תדיר בשימושים של תורת המספרים; לדוגמה, בשיטת ההצפנה [[RSA]].
 
בחישוב המבנה של חבורת אוילר עסק [[קרל פרידריך גאוס|גאוס]], שמצא כי החבורה [[חבורה ציקלית|ציקלית]] בדיוק כאשר n שווה ל- 1, 2, 4, חזקה של מספר ראשוני אי-זוגי, או פעמיים חזקה כזו (ראו [[איבר פרימיטיבי]]).
 
==המבנה של חבורת אוילר==
שורה 15:
כאשר p ראשוני, חבורת אוילר <math>\ U_p</math> היא ציקלית. לדוגמה, החבורה <math>\ U_{13}</math> נוצרת על ידי 2. לעובדה שתמיד קיימים יוצרים קטנים יחסית של החבורה יש חשיבות רבה ב[[מבחן ראשוניות|מבחני ראשוניות]]. טענה זו, על הציקליות של <math>\ U_p</math>, היא מקרה פרטי של משפט כללי יותר - תת-חבורה כפלית, סופית, של [[שדה (מבנה אלגברי)|שדה]] היא תמיד ציקלית. כדי להוכיח את הטענה, יש להבחין כי למשוואה <math>\ x^d=1</math> יש (בשדה) לכל היותר d פתרונות; מצד שני, אם d מחלק את p-1, אז הפולינום <math>\ x^{d}-1</math> מחלק את הפולינום <math>\ x^{p-1}-1</math>, וכך אפשר לראות שלמשוואה יש בדיוק d פתרונות. אם <math>\ r_d</math> יסמן את מספרם של המספרים שסדרם שווה ל- d, אפשר להוכיח באינדוקציה על d את השוויון <math>\ r_d=\phi(d)</math>.
 
כדי לראות שחבורת אוילר ציקלית גם עבור חזקות <math>\ p^t</math>, די להצביע על איבר מסדר <math>\ p^{t-1}</math> (מכפלתו של איבר כזה באיבר מסדר p-1 היא מסדר <math>\ \phi(p^t)=(p-1)p^{t-1}</math>). ואכן, כאשר p אי-זוגי, האיבר p+1 הוא כזה. לדוגמה, בחבורה <math>\ U_{3125}</math>, לאיבר 2057 יש סדר 4, ואילו ל- 6 יש סדר 625. המכפלה, 2967, יוצרת את החבורה.
 
במקרה של חזקת 2 החבורה אינה ציקלית, ובמקום זה <math>\ U_{2^t} \cong \mathbb{Z}/2\mathbb{Z}\times \mathbb{Z}/2^{t-2}\mathbb{Z}</math> (כאשר <math>\ t\geq 3</math>). את החבורה יוצרים המספרים <math>\ U_{2^t}=\langle -1,5\rangle</math>.
 
כך אפשר לפרק את חבורת אוילר באופן כללי. למשל,
<math>\ 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}</math>, ומכאן שה[[אקספוננט של חבורה|אקספוננט]] של חבורה זו הוא <math>\ 16\cdot 5=80</math>. במלים אחרות, לכל a שאינו מתחלק ב- 2 או ב- 5, מתקיים <math>\ a^{80} \equiv 1\pmod{1600}</math>, והמספר 80 הוא הקטן ביותר בעל תכונה זו.
 
את האקספוננט של חבורת אוילר מסדר n מסמנים ב-<math>\ \lambda(n)</math>, בעוד שפונקציית אוילר של <math>\ n = p_1^{s_1}\dots 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>\ 2 \leq s</math>).