משפט לגראנז' (פולינומים)

בתורת המספרים האלמנטרית, משפט לגראנז' על קונגרואנציות פולינומיות נותן חסם עליון לשכיחות שבה פולינום במקדמים שלמים עשוי לקבל ערכים שהם כפולות של מספר ראשוני נתון. בניסוח פורמלי, המשפט קובע כי אם p הוא מספר ראשוני ו- $\textstyle f(x)\in \mathbb {Z} [x]$ הוא פולינום במקדמים שלמים, אז מתקיים אחד מהדברים הבאים:

• כל המקדמים של (f(x מתחלקים ב-p, או
• לקונגרואנציה (f(x) ≡ 0 (mod p יש לכל היותר (deg f(x פתרונות לא שקולים.

פתרונות הם "לא שקולים" אם הם אינם שקולים מודולו p. אם הקונגרואנציה הפולינומית מחושבת ביחס למספר פריק, אז ייתכן שיהיו לה יותר מ-(deg f(x פתרונות.

המשפט נקרא על שם ז'וזף לואי לגראנז' שהוכיח אותו ב-1777.

הוכחה של משפט לגראנז'

את המשפט נוכיח באינדוקציה; המצב עבור n = 1 ברור, ולכן ניתן לבחור בו כבסיס האינדוקציה. נניח כעת $n\geq 2$, ושהטענה מתקיימת לכל הפולינומים ממעלה קטנה מ-n. הפולינום $\textstyle f(x)\in \mathbb {Z} [x]$ אינו מתאפס מודולו p, או שיש לו לפחות אפס אחד, נניח ב-$x=a$. אם נגדיר פולינום חדש $f(x)-f(a)$ אז נקבל שיש לו שורש ב-x = a ולכן הוא ניתן להצגה גם כך: $(x-a)g(x)$. מכיוון שלכל מספר טבעי m מתקיים ש- ${\frac {x^{m}-a^{m}}{x-a}}$ הוא פולינום ממעלה m - 1 במקדמים שלמים, נובע מכך ש-$\textstyle g(x)\in \mathbb {Z} [x]$ ושהוא ממעלה n-1. כיוון ש-:

$f(x)=(x-a)g(x)+f(a)\equiv (x-a)g(x){\pmod {p}}$

מראשוניותו של p נובע שלכל x המקיים $f(x)\equiv 0{\pmod {p}}$ מתקיים ש- $x\equiv a{\pmod {p}}$ או ש- $g(x)\equiv 0{\pmod {p}}$ או שניהם. לפי הנחת האינדוקציה לקונגרואנציה $g(x)\equiv 0{\pmod {p}}$ יש לכל היותר $deg(g(x))=n-1$ פתרונות, ומכאן נובע שמספר הפתרונות ל- $f(x)\equiv 0{\pmod {p}}$ הוא לכל היותר $1+(n-1)=n$.

מ.ש.ל

הערה: המשפט אינו נכון באופן כללי כאשר הקונגרואנציות מחושבות ביחס למספר פריק. כדוגמה מספרית ניקח את $x^{2}\equiv 1{\pmod {8}}$. זוהי קונגרואנציה ממעלה 2, אך עם זאת יש לה 4 פתרונות לא שקולים, שהם 7, 5, 3, 1 מודולו 8.

הערך באדיבות ויקיפדיה העברית, קרדיט,
רשימת התורמים
רישיון cc-by-sa 3.0

30421643משפט לגראנז' (פולינומים)