הצגת המקור של הדף "משפט לגראנז' (פולינומים)"

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

יהי <math>p</math> מספר ראשוני ויהי <math>f(x)\in\Z[x]</math> פולינום במקדמים שלמים. אזי ישנן שתי אפשרויות:
*כל מקדמי הפולינום מתחלקים ב-<math>p</math>. או:
*לקונגרואנציה <math>f(x)\equiv0\!\!\!\pmod{p}</math> לכל היותר <math>\deg\!\bigl(f(x)\bigr)</math> פתרונות שונים [[חשבון מודולרי|מודולו]] <math>p</math>.
אם הקונגרואנציה הפולינומית מחושבת מודולו [[מספר פריק]], אז ייתכן שיהיו לה יותר מ-<math>\deg\!\bigl(f(x)\bigr)</math> פתרונות.

==הוכחה==
נוכיח ב[[אינדוקציה מתמטית|אינדוקציה]].

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

נניח כי לכל פולינום ממעלה <math>n=k</math> ישנם לכל היותר <math>k</math> פתרונות שונים מודולו <math>p</math>. יהי <math>f(x)\in\Z[x]</math> פולינום ממעלה <math>k+1</math>. ישנן שתי אפשרויות:
#לקונגרואנציה <math>f(x)\equiv0\!\!\!\pmod{p}</math> אין פתרון, וסיימנו.
#לקונגרואנציה לפחות פתרון אחד <math>x=a</math>. אזי נקבל <math>f(x)=(x-a)q(x)+f(a)</math>, כאשר <math>q(x)\in\Z[x]</math> פולינום ממעלה <math>k</math>. 
::מכאן <math>f(a)=(a-a)q(a)+f(a)\equiv0\!\!\!\pmod{p}</math>, כלומר <math>f(x)\equiv(x-a)q(x)\!\!\!\pmod{p}</math>.
::כל פתרון אחר <math>x=b\not\equiv a\!\!\!\pmod{p}</math> מקיים <math>f(b)\equiv(b-a)q(b)\equiv0\!\!\!\pmod{p}</math>, כלומר <math>q(b)\equiv0\!\!\!\pmod{p}</math>.
::מהנחת האינדוקציה, לקונגרואנציה <math>q(x)\equiv0\!\!\!\pmod{p}</math> לכל היותר <math>k</math> פתרונות שונים מודולו <math>p</math>.
::לכן לקונגרואנציה <math>f(x)\equiv0\!\!\!\pmod{p}</math> לכל היותר <math>k+1</math> פתרונות שונים מודולו <math>p</math>.

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

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