שינויים

קפיצה אל: ניווט, חיפוש

מבנים אלגבריים למדעי המחשב - ארז שיינר

נוספו 755 בתים, 17:52, 20 באוקטובר 2018
/* תת חבורות ציקליות */
*הוכחה:
**ראשית נוכיח עבור המקרה בו סדר האיבר סופי <math>o(a)=n</math>.
***רוצים להוכיח כי <math><a>=\{e_G,a,a^2,...,a_{n-1}\}</math> וכי כל האיברים בקבוצה זו שונים זה מזה (אחרת כמות האיברים קטנה יותר מn).***ברור שהחזקות של a שייכות לתת החבורה הציקלית.***יהי k כלשהו, נסמן בr את השארית <math>r=k \mod n</math> כלומר <math>k=pn+r</math> עבור <math>p\in\mathbb{Z}, 0\leq r\leq n-1</math>.***<math>a^k=(a^n)^pa^r=e_G^pa^r=a_r</math>.***כעת נניח כי קיימות שתי חזקות שונות <math>0\leq r_1<r_2\leq n-1</math> כך ש <math>a^{r_1}=a^{r_2}</math>.***לכן <math>a^{r_2-r_1}=e_G</math>.***אבל <math>r_2-r_2\leq n-1 < n</math> בסתירה לכך ש<math>o(a)=n</math>.