למת הנזל – הבדלי גרסאות
תוכן שנמחק תוכן שנוסף
MathKnight (שיחה | תרומות) אין תקציר עריכה |
MathKnight (שיחה | תרומות) אין תקציר עריכה |
||
שורה 1:
'''למת הנזל''' היא [[משפט מתמטי]] ב[[תורת המספרים]], המאפשר למצוא פתרון ל[[חשבון מודולרי|קונגרואנציה]]
== ניסוח הלמה ==
שורה 21:
אם <math>f'(r) \equiv 0 \pmod{p}\,</math> ו <math>f(r) \not\equiv 0 \pmod{p^k}
== הוכחת הלמה ==
נרשום [[טור טיילור|פיתוח טיילור]] לפולינום שלנו
: <math>\ f(r + tp^{k-1}) = f(r) + f'(r) t p^{k-1} + \sum_{m=2}^{n}{f^{(n)}(r) (t p^{k-1})^m / m!}</math>
וזהו פולינום ב-t עם מקדמים שלמים.
נשים לב שמודולו <math>p^k</math> כל האיברים בסכום מ m=2 עד n שווים לאפס. <br />
לכן, דורשים ש <math>\ R = r + t p^{k-1}</math>יהיה פתרון ומקבלים ש
: <math>\ 0 = f(r + tp^{k-1}) = f(r) + f'(r) t p^{k-1} \pmod{p^k} </math>
או אם נעביר אגפים ונחלק ב <math>p^{k-1}</math>, נקבל ש
: <math>\ f'(r) t = -f(r) / p^{k-1} \pmod{p}</math>.
זוהי [[קונגרואנציה ליניארית]] ב-t ולה יש פתרון יחיד בתנאי ש <math>f'(r) \not\equiv 0 \pmod{p}</math>. במקרה זה הפתרון הוא כפי שנתון בניסוח הלמה.
אם <math>f'(r) \equiv 0 \pmod{p}</math> קל לראות שיש פתרון רק אם אגף ימין קונגרואנטי לאפס גם הוא, ואז זה מצב של <math>\ 0 \cdot t = 0</math> וכל t פתרון. אחרת, קל לראות שאין פתרון.
== דוגמה ==
יהי
[[קטגוריה:תורת המספרים]]
| |||