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

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

יהי  מספר ראשוני ויהי  פולינום במקדמים שלמים. אזי ישנן שתי אפשרויות:
כל מקדמי הפולינום מתחלקים ב-. או:
לקונגרואנציה  לכל היותר  פתרונות שונים מודולו .
אם הקונגרואנציה הפולינומית מחושבת מודולו מספר פריק, אז ייתכן שיהיו לה יותר מ- פתרונות.

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

עבור  נקבל פולינום ליניארי .
לקונגרואנציה ליניארית  קיים פתרון מודולו  אם ורק אם , כאשר  – ובמקרה זה זהו גם מספר הפתרונות השונים מודולו .
אם : לקונגרואנציה  פתרון יחיד מודולו .
אם : אם  אזי מתקיימת האפשרות הראשונה, ואם  אזי לקונגרואנציה אין פתרון.

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

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

קטגוריה:משפטים בתורת המספרים
קטגוריה:פולינומים