שאלה 2
סעיף א'
הוכח את משפט אוילר על החזקות ופתור את המשוואה
פתרון
משפט אוילר על החזקות אומר שאם אז
. אבל אם
אז לפי משפט,
. אחת התוצאות של משפט לגרנז' אומרת שאם מעלים איבר בחזקת סדר של החבורה, נקבל את הנטרלי של החבורה. במקרה הזה, הנטרלי הוא 1 והסדר של החבורה הוא
. נזכור שההגדרה של
היא בעצם
ולכן קיבלנו
.
כעת נפתור את המשוואה. כיוון ש- 31 ראשוני, אז לפי משפט וילסון, וכיוון ש-30 הפיך ב-
אפשר להסיק ש-
. קיבלנו:
.
נזכור ש- (אם p ראשוני אז
) ולכן לפי המשפט שהוכחנו,
ומכאן
. קל לחשב ש-
ולכן קיבלנו את המשוואה:
. עוד נראה ש-
ולכן
ומכאן ש-