צפה בגרסה המלאה : מציאת אי קיום פתרון למשוואה
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}$ ומכאן לא אמור להיות בעייתי להמשיך.
vBulletin v4.2.5, Copyright ©2000-2021, Jelsoft Enterprises Ltd.