שינויים

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

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

אין שינוי בגודל, 15:59, 27 באוקטובר 2018
/* תת חבורות ציקליות */
*הוכחה:
**ראשית נוכיח עבור המקרה בו סדר האיבר סופי <math>o(a)=n</math>.
***רוצים להוכיח כי <math><a>=\{e_G,a,a^2,...,a_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_ra^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>.