מתוך ויקיפדיה, האנציקלופדיה החופשית
בתורת המספרים , משפט לגראנז' על קונגרואנציות פולינומיות (על שם המתמטיקאי והאסטרונום האיטלקי ז'וזף לואי לגראנז' ) נותן חסם עליון לשכיחות שבה פולינום במקדמים שלמים עשוי לקבל ערכים שהם כפולות של מספר ראשוני נתון.
יהי
p
{\displaystyle p}
מספר ראשוני ויהי
f
(
x
)
∈
Z
[
x
]
{\displaystyle f(x)\in \mathbb {Z} [x]}
פולינום במקדמים שלמים. אזי ישנן שתי אפשרויות:
כל מקדמי הפולינום מתחלקים ב-
p
{\displaystyle p}
. או:
לקונגרואנציה
f
(
x
)
≡
0
(
mod
p
)
{\displaystyle f(x)\equiv 0\!\!\!{\pmod {p}}}
לכל היותר
deg
(
f
(
x
)
)
{\displaystyle \deg \!{\bigl (}f(x){\bigr )}}
פתרונות שונים מודולו
p
{\displaystyle p}
.
אם הקונגרואנציה הפולינומית מחושבת מודולו מספר פריק , אז יתכן שיהיו לה יותר מ-
deg
(
f
(
x
)
)
{\displaystyle \deg \!{\bigl (}f(x){\bigr )}}
פתרונות.
נוכיח באינדוקציה .
עבור
n
=
1
{\displaystyle n=1}
נקבל פולינום ליניארי
f
(
x
)
=
a
1
x
+
a
0
{\displaystyle f(x)=a_{1}x+a_{0}}
.
לקונגרואנציה ליניארית
a
x
≡
b
(
mod
m
)
{\displaystyle ax\equiv b\!\!\!{\pmod {m}}}
קיים פתרון מודולו
m
{\displaystyle m}
אם ורק אם
d
∣
b
{\displaystyle d\mid b}
, כאשר
d
=
gcd
{
a
,
m
}
{\displaystyle d=\gcd\{a,m\}}
– ובמקרה זה זהו גם מספר הפתרונות השונים מודולו
m
{\displaystyle m}
.
אם
gcd
{
a
1
,
p
}
=
1
{\displaystyle \gcd\{a_{1},p\}=1}
: לקונגרואנציה
a
1
x
≡
−
a
0
(
mod
p
)
{\displaystyle a_{1}x\equiv -a_{0}\!\!\!{\pmod {p}}}
פתרון יחיד מודולו
p
{\displaystyle p}
.
אם
gcd
{
a
1
,
p
}
=
p
{\displaystyle \gcd\{a_{1},p\}=p}
: אם
p
∣
a
0
{\displaystyle p\mid a_{0}}
אזי מתקיימת האפשרות הראשונה, ואם
p
∤
a
0
{\displaystyle p\nmid a_{0}}
אזי לקונגרואנציה אין פתרון.
נניח כי לכל פולינום ממעלה
n
=
k
{\displaystyle n=k}
ישנם לכל היותר
k
{\displaystyle k}
פתרונות שונים מודולו
p
{\displaystyle p}
. יהי
f
(
x
)
∈
Z
[
x
]
{\displaystyle f(x)\in \mathbb {Z} [x]}
פולינום ממעלה
k
+
1
{\displaystyle k+1}
. ישנן שתי אפשרויות:
לקונגרואנציה
f
(
x
)
≡
0
(
mod
p
)
{\displaystyle f(x)\equiv 0\!\!\!{\pmod {p}}}
אין פתרון, וסיימנו.
לקונגרואנציה לפחות פתרון אחד
x
=
a
{\displaystyle x=a}
. אזי נקבל
f
(
x
)
=
(
x
−
a
)
q
(
x
)
+
f
(
a
)
{\displaystyle f(x)=(x-a)q(x)+f(a)}
, כאשר
q
(
x
)
∈
Z
[
x
]
{\displaystyle q(x)\in \mathbb {Z} [x]}
פולינום ממעלה
k
{\displaystyle k}
.
מכאן
f
(
a
)
=
(
a
−
a
)
q
(
a
)
+
f
(
a
)
≡
0
(
mod
p
)
{\displaystyle f(a)=(a-a)q(a)+f(a)\equiv 0\!\!\!{\pmod {p}}}
, כלומר
f
(
x
)
≡
(
x
−
a
)
q
(
x
)
(
mod
p
)
{\displaystyle f(x)\equiv (x-a)q(x)\!\!\!{\pmod {p}}}
.
כל פתרון אחר
x
=
b
≢
a
(
mod
p
)
{\displaystyle x=b\not \equiv a\!\!\!{\pmod {p}}}
מקיים
f
(
b
)
≡
(
b
−
a
)
q
(
b
)
≡
0
(
mod
p
)
{\displaystyle f(b)\equiv (b-a)q(b)\equiv 0\!\!\!{\pmod {p}}}
, כלומר
q
(
b
)
≡
0
(
mod
p
)
{\displaystyle q(b)\equiv 0\!\!\!{\pmod {p}}}
.
מהנחת האינדוקציה, לקונגרואנציה
q
(
x
)
≡
0
(
mod
p
)
{\displaystyle q(x)\equiv 0\!\!\!{\pmod {p}}}
לכל היותר
k
{\displaystyle k}
פתרונות שונים מודולו
p
{\displaystyle p}
.
לכן לקונגרואנציה
f
(
x
)
≡
0
(
mod
p
)
{\displaystyle f(x)\equiv 0\!\!\!{\pmod {p}}}
לכל היותר
k
+
1
{\displaystyle k+1}
פתרונות שונים מודולו
p
{\displaystyle p}
.
הערה : המשפט אינו נכון באופן כללי כאשר הקונגרואנציות מחושבות ביחס למספר פריק. כדוגמה מספרית ניקח את
x
2
≡
1
(
mod
8
)
{\displaystyle x^{2}\equiv 1\!\!\!{\pmod {8}}}
. זוהי קונגרואנציה ממעלה 2, אך עם זאת יש לה 4 פתרונות לא שקולים, שהם 7, 5, 3, 1 מודולו 8.