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

בתורת המספרים, משפט לגראנז' על קונגרואנציות פולינומיות (על שם המתמטיקאי והאסטרונום האיטלקי ז'וזף לואי לגראנז') נותן חסם עליון לשכיחות שבה פולינום במקדמים שלמים עשוי לקבל ערכים שהם כפולות של מספר ראשוני נתון.

יהי $p$ מספר ראשוני ויהי $f(x)\in \mathbb {Z} [x]$ פולינום במקדמים שלמים. אזי ישנן שתי אפשרויות:

• כל מקדמי הפולינום מתחלקים ב-$p$. או:
• לקונגרואנציה $f(x)\equiv 0\!\!\!{\pmod {p}}$ לכל היותר $\deg \!{\bigl (}f(x){\bigr )}$ פתרונות שונים מודולו $p$.

אם הקונגרואנציה הפולינומית מחושבת מודולו מספר פריק, אז יתכן שיהיו לה יותר מ-$\deg \!{\bigl (}f(x){\bigr )}$ פתרונות.

הוכחה

נוכיח באינדוקציה.

עבור $n=1$ נקבל פולינום ליניארי $f(x)=a_{1}x+a_{0}$.
לקונגרואנציה ליניארית $ax\equiv b\!\!\!{\pmod {m}}$ קיים פתרון מודולו $m$ אם ורק אם $d\mid b$, כאשר $d=\gcd\{a,m\}$ – ובמקרה זה זהו גם מספר הפתרונות השונים מודולו $m$.
אם $\gcd\{a_{1},p\}=1$: לקונגרואנציה $a_{1}x\equiv -a_{0}\!\!\!{\pmod {p}}$ פתרון יחיד מודולו $p$.
אם $\gcd\{a_{1},p\}=p$: אם $p\mid a_{0}$ אזי מתקיימת האפשרות הראשונה, ואם $p\nmid a_{0}$ אזי לקונגרואנציה אין פתרון.

נניח כי לכל פולינום ממעלה $n=k$ ישנם לכל היותר $k$ פתרונות שונים מודולו $p$. יהי $f(x)\in \mathbb {Z} [x]$ פולינום ממעלה $k+1$. ישנן שתי אפשרויות:

1. לקונגרואנציה $f(x)\equiv 0\!\!\!{\pmod {p}}$ אין פתרון, וסיימנו.
2. לקונגרואנציה לפחות פתרון אחד $x=a$. אזי נקבל $f(x)=(x-a)q(x)+f(a)$, כאשר $q(x)\in \mathbb {Z} [x]$ פולינום ממעלה $k$.

מכאן $f(a)=(a-a)q(a)+f(a)\equiv 0\!\!\!{\pmod {p}}$, כלומר $f(x)\equiv (x-a)q(x)\!\!\!{\pmod {p}}$.

כל פתרון אחר $x=b\not \equiv a\!\!\!{\pmod {p}}$ מקיים $f(b)\equiv (b-a)q(b)\equiv 0\!\!\!{\pmod {p}}$, כלומר $q(b)\equiv 0\!\!\!{\pmod {p}}$.

מהנחת האינדוקציה, לקונגרואנציה $q(x)\equiv 0\!\!\!{\pmod {p}}$ לכל היותר $k$ פתרונות שונים מודולו $p$.

לכן לקונגרואנציה $f(x)\equiv 0\!\!\!{\pmod {p}}$ לכל היותר $k+1$ פתרונות שונים מודולו $p$.

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