PDA

צפה בגרסה המלאה : מציאת אי קיום פתרון למשוואה



Doom's_Day
10-06-2016, 17:39
שלום

אשמח אם תוכלו לעוזר לי עם הוכחת אי קיום של פתרון למשוואה:

(x3=2(mod 151



תודה לעוזרים ושבת שלום

avishay12456
12-06-2016, 23:29
הדרכה: נניח בשלילה שקיים פתרון למשוואה, נסמן אותו ב-x. נשים לב כי $\textrm{ord}_{151}(2)=15$ ולכן $x^{45}\equiv 1 \mod 151$ ולכן $\textrm{ord}_{151}(x) | 45$. מכאן שהסדר של x חייב להיות 45 / 15 / 9 / 5 / 3 / 1. תנסה לפסול את כולם ובכך לקבל סתירה. אני מצרף הדרכה לכל אחד מהמקרים בספוילר.


1 - ברור למה נפסל.
האפשרויות שמתחלקות ב-3 חוץ מ-45 - הסדר של 2 הוא 15 ובכל אחד מהמקרים האלה מקבלים סדר קטן יותר.
45 - $\varphi(151)=150$ ו-45 לא מחלק את 150.
5 - יותר טריקי מהאחרים. בדר"כ gcd זה כיוון טוב לשאלות. מתקיים $1=2\cdot 3+(-1)\cdot 5$ (האלגוריתם המורחב של אוקלידס) ולכן $x=x^1=x^{2\cdot 3+(-1)\cdot 5}=(x^3)^2\cdot (x^5)^{-1}$ ומכאן לא אמור להיות בעייתי להמשיך.