חלוקת פולינומים

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

האלגוריתם מיישם הלכה למעשה את תכונת הפולינומים הבאה:
בהינתן פולינומים
:A(x)=a_nx^n+a_{n-1}x^{n-1}+\cdots+a_1x+a_0 (**מחולק**)
:B(x)=b_mx^m+b_{m-1}x^{m-1}+\cdots+b_1x+b_0 (**מחלק**)
כאשר m=\deg(B(x))\le\deg(A(x))=n, ניתן לכתוב A(x)=B(x)Q(x)+R(x) עבור פולינום Q(x) שיקרא **המנה** ועבור פולינום R(x) שיקרא **שארית החלוקה**, כאשר \deg(R(x)).

התוצאה R(x)=0 תופיע אם ורק אם B(x) הוא גורם של A(x), כלומר ניתן לרשום A(x)=B(x)Q(x).
בנוסף, על פי המשפט הקטן של בזו, אם x=a הוא שורש של A(x), דהיינו A(a)=0, אזי x-a הוא גורם של A(x). לכן, נעשה שימוש נרחב בחלוקת פולינומים הן על מנת לפרק את הפולינום לגורמים והן על מנת לפשט את הליך מציאת השורשים הנוספים שלו, אם אחד מהם כבר ידוע.

## דוגמה לאופן פעולת האלגוריתם
נמצא את מנת החלוקה ואת השארית שלה עבור חלוקת הפולינום A(x)=x^3-2x^2-4 (המחולק) בפולינום B(x)=x-3 (המחלק).

תחילה נכתוב מחדש את המחולק באופן הבא:
:A(x)=x^3-2x^2+0x-4
כעת נבצע את התהליך דלהלן:

נחלק את '''המונום המוביל''' (האיבר בעל החזקה המרבית) של A(x) במונום המוביל של B(x), במקרה זה, מדובר ב-(x^3 / x=x^2). את התוצאה נכתוב מעל לקו האופקי:
:\begin{array}{l}{\color{White} x-3 )}x^2\\\overline{x^3-2x^2+0x-4}\,\vert{\,x-3}\end{array}
*נכפול את כל איברי המחלק בתוצאה שקיבלנו זה עתה, ונקבל x^2B(x)=x^3-3x^2. נכתוב את התוצאה תחת האיברים הראשונים של המחולק:
:\begin{array}{l}{\color{White}x-3 )}x^2\\\overline{x^3-2x^2+0x-4}\,\vert{\,x-3}\\{\color{White}}x^3-3x^2\end{array}
*נחסר את התוצאה שרשמנו מהאיברים שמעליה ומיד לאחר מכן, נעתיק מטה את האיבר הראשון מימין לאיברי המחלק שביצענו עליהן כעת פעולה.
:\begin{array}{l}{\color{White}x-3 )}x^2\\\overline{x^3-2x^2+0x-4}\,\vert{\,x-3}\\{\color{White}}\underline{x^3-3x^2}\\{\color{White}0x^3}+{\color{White}}x^2+0x\end{array}
*נבצע כעת שוב את אותה סדרת פעולות עבור הפולינום החדש שהתקבל מההפרש ומהוספת האיבר הנוסף.
:
\begin{array}{r}
 x^2+x {\color{White} ^3-2x^2+0}\\
 \overline{x^3-2x^2+0x-4}\,\vert{\,x-3}\\
 \underline{x^3-3x^2 {\color{White} -2x^2+0x-4}}\\
 +x^2+0x {\color{White} {} ^2+0x-4}\\
 \underline{+x^2-3x {\color{White} {} ^2+0x-4}}\\
 +3x-4 {\color{White} {}   0x-4}\end{array}

*כעת, לא ניתן להעתיק מטה אף איבר. נסיים את התהליך.
:
\begin{array}{r}
 x^2+ {} x+3 {\color{White} ^3-2x^2  }\\
 \overline{x^3-2x^2+0x-4}\,\vert{\,x-3}\\
 \underline{x^3-3x^2 {\color{White} x^3-2x^2+0x-}}\\
 +x^2 + 0x {\color{White} {} x^3-2x^2+ }\\
 \underline{+x^2-3x {\color{White} {} x^3-2x^2+}}\\
 { +3x-4 {\color{White} {}   0x-4}}\\
 \underline{+3x-9{\color{White} {}   0x-4}}\\
 +5 {\color{White} {}  0x-4}\\
\end{array}


הפולינום שהתקבל מעל לקו האופקי הוא המנה Q(x)=x^2+x+3 והפולינום, במקרה זה ממעלה 0, שנותר אחרי הפעולה האחרונה, הוא השארית R(x)=5. לכן קיבלנו כי
:\underbrace{x^3-2x^2-4}_{A(x)}=\underbrace{(x-3)}_{B(x)}\,\underbrace{(x^2+x+3)}_{Q(x)}+\underbrace{5}_{R(x)}

## שימושים
### פירוק פולינומים לגורמים
בהינתן פולינום, לעיתים, שורש אחד או יותר שלו כבר ידועים אך ייתכן כי קיימים לו כאלו נוספים. אם ידוע כי r הוא שורש של פולינום P(x)=a_nx^n+a_{n-1}x^{n-1}+...+a_1x+a_0 - פולינום ממעלה n, כלומר מתקיים כי P(r)=a_nr^n+a_{n-1}r^{n-1}+...+a_1r+a_0=0, ניתן לחלק את P(x) ב-(x-r) ומהמשפט הקטן של בזו נובע כי שארית החלוקה היא 0. לכן, נקבל במקרה זה כי P(x)=(x-r)Q(x) עבור Q(x)=b_{n-1}x^{n-1}+b_{n-2}x^{n-2}+...+b_1x+b_0, כלומר דרגת המנה היא n-1. בחלק מהמקרים, הפולינום Q(x)=b_{n-1}x^{n-1}+b_{n-2}x^{n-2}+...+b_1x+b_0 הוא כזה שקל יותר למצוא את שורשיו. מאחר שכל שורש שלו הוא גם שורש של P(x)=a_nx^n+a_{n-1}x^{n-1}+...+a_1x+a_0, הרי שבכך יועל תהליך מציאת השורשים של הפולינום המקורי.

באופן דומה, אם ידועים יותר משורש אחד של הפולינום, לדוגמה, ידוע כי r_1,r_2,...,r_k שורשים שלו, ניתן לחלק את הפולינום ב-(x-r_1) ולקבל P(x)=(x-r_1)Q_1(x). כעת, ניתן לחלק את Q_1(x) ב-(x-r_2) ולקבל כי Q_1(x)=(x-r_2)Q_2(x) כך שדרגתו של Q_2(x) קטנה מהדרגה של Q_1(x). לכן, P(x)=(x-r_1)(x-r_2)Q_2(x). כעת, ניתן להמשיך את התהליך, עד שבסופו של דבר יתקבל כי P(x)=(x-r_1)(x-r_2)\cdot\cdot\cdot(x-r_k)Q_k(x) כך שדרגת P(x)=-Q_k(x) קטנה מ-n-k.

### מציאת ישר משיק לנקודה על גרף של פונקציה פולינומית
ניתן להשתמש בחלוקת פולינומים גם למציאת משוואת הישר המשיק לנקודה הנמצאת על גרף של פונקציה פולינומית. בהינתן פונקציה f(x)=a_nx^n+a_{n-1}x^{n-1}+...+a_1x+a_0 ונקודה x=q, משוואת המשיק לגרף בנקודה x=q תהיה שארית החלוקה של f(x) ב-(x-q)^2.

#### דוגמה
נמצא את משוואת הישר המשיק לפונקציה y =f(x)= x^3 - 12x^2 - 42 בנקודה x=1.
:נחלק את הפולינום ב-(x-1)^2 = x^2-2x+1:
:: 
\begin{array}{r}
 x - 10\\
 x^2-2x+1\overline{) x^3 - 12x^2 + 0x - 42}\\
 \underline{x^3 - {\color{White}0}2x^2 + {\color{White}1}x} {\color{White} {} - 42}\\
 -10x^2 - {\color{White}01}x - 42\\
 \underline{-10x^2 + 20x - 10}\\
 -21x - 32
\end{array}

לכן, משוואת המשיק המבוקשת היא y = - 21 x - 32.

### בדיקת יתירות מחזורית

בבדיקת יתירות מחזורית משתמשים בשארית החלוקה של פולינומים עבור ניטור שגיאות בהעברת מסרים.

## ראו גם
* המשפט הקטן של בזו
* חוג אוקלידי

## קישורים חיצוניים
* 
* 

## הערות שוליים

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