אלגברה מופשטת 1- מועד א' קיץ תשע"ג

שאלה 2

סעיף א'

הוכח את משפט אוילר על החזקות ופתור את המשוואה [math]\displaystyle{ 16x\equiv 29!\cdot 25^{92} \operatorname{mod}31 }[/math]

פתרון

משפט אוילר על החזקות אומר שאם [math]\displaystyle{ (a,n)=1 }[/math] אז [math]\displaystyle{ a^{\varphi(n)}\equiv 1 \operatorname{mod} n }[/math]. אבל אם [math]\displaystyle{ (a,n)=1 }[/math] אז לפי משפט, [math]\displaystyle{ a \in U_n }[/math]. אחת התוצאות של משפט לגרנז' אומרת שאם מעלים איבר בחזקת סדר של החבורה, נקבל את הנטרלי של החבורה. במקרה הזה, הנטרלי הוא 1 והסדר של החבורה הוא [math]\displaystyle{ |U_n| }[/math]. נזכור שההגדרה של [math]\displaystyle{ \varphi(n) }[/math] היא בעצם [math]\displaystyle{ |U_n| }[/math] ולכן קיבלנו [math]\displaystyle{ a^{\varphi(n)}\equiv 1\operatorname{mod} n }[/math].

כעת נפתור את המשוואה. כיוון ש- 31 ראשוני, אז לפי משפט וילסון, [math]\displaystyle{ 30!\equiv 30 \operatorname{mod}31 }[/math] וכיוון ש-30 הפיך ב- [math]\displaystyle{ \mathbb{Z}_{31} }[/math] אפשר להסיק ש- [math]\displaystyle{ 29!\equiv 1 \operatorname{mod} 31 }[/math]. קיבלנו: [math]\displaystyle{ 16x\equiv 1\cdot 25^{92} \operatorname{mod}31 }[/math].

נזכור ש- [math]\displaystyle{ \varphi(31)=30 }[/math] (אם p ראשוני אז [math]\displaystyle{ \varphi(p)=p-1 }[/math]) ולכן לפי המשפט שהוכחנו, [math]\displaystyle{ 25^{30}\equiv 1 \operatorname{mod}31 }[/math] ומכאן [math]\displaystyle{ 25^{92}=25^{30}\cdot 25^{30}\cdot 25^{30}\cdot 25^2 \equiv 1\cdot 1\cdot 1\cdot 25^2 \operatorname{mod}31 }[/math]. קל לחשב ש- [math]\displaystyle{ 25^2\equiv 5 \operatorname{mod}31 }[/math] ולכן קיבלנו את המשוואה: [math]\displaystyle{ 16x\equiv 5 \operatorname{mod}31 }[/math]. עוד נראה ש- [math]\displaystyle{ 2\cdot 16 \equiv 1 \operatorname{mod} 31 }[/math] ולכן [math]\displaystyle{ 2\cdot 16x \equiv 2\cdot 5 \operatorname{mod}31 }[/math] ומכאן ש- [math]\displaystyle{ x\equiv 10 \operatorname{mod}31 }[/math]