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

שאלה 2

סעיף א'

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

פתרון

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

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

נזכור ש- $\varphi(31)=30$ (אם p ראשוני אז $\varphi(p)=p-1$) ולכן לפי המשפט שהוכחנו, $25^{30}\equiv 1 \operatorname{mod}31$ ומכאן $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$. קל לחשב ש- $25^2\equiv 5 \operatorname{mod}31$ ולכן קיבלנו את המשוואה: $16x\equiv 5 \operatorname{mod}31$. עוד נראה ש- $2\cdot 16 \equiv 1 \operatorname{mod} 31$ ולכן $2\cdot 16x \equiv 2\cdot 5 \operatorname{mod}31$ ומכאן ש- $x\equiv 10 \operatorname{mod}31$