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

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

האלגוריתם מיישם הלכה למעשה את תכונת הפולינומים הבאה. בהינתן $P(x)=a_{n}x^{n}+a_{n-1}x^{n-1}+...+a_{1}x+a_{0}$ (מחולק) ו- $D(x)=b_{k}x^{k}+b_{k-1}x^{k-1}+...+b_{1}x+b_{0}$ (מחלק) כך ש- $k\leq n$ ובניסוח מדויק, $\deg(D(x))\leq \deg(P(x))$ , ניתן לבטא את $P(x)$ כ- $P(x)=D(x)Q(x)+R(x)$ עבור $Q(x)$ פולינום שיקרא המנה ועבור $R(x)$ פולינום שיקרא שארית החלוקה, כך שדרגת השארית $R(x)$ קטנה (ממש) מדרגת המחלק $D(x)$ , כלומר $\deg(R(x))<\deg(D(x))$ .

התוצאה $R(x)=0$ תופיע אם ורק אם $D(x)$ הוא גורם של $P(x)$ , כלומר, ניתן לרשום את $P(x)$ כמכפלה של הפולינום $D(x)$ בפולינום אחר. בנוסף, על פי המשפט הקטן של בזו, אם $a$ הוא שורש של $P(x)$ , דהיינו $P(a)=0$ , אזי $(x-a)$ הוא גורם של $P(x)$ . לכן, נעשה שימוש נרחב בחלוקת פולינומים הן על מנת לפרק את הפולינום לגורמים והן על מנת לפשט את הליך מציאת השורשים הנוספים שלו, אם אחד מהם כבר ידוע^[3].

דוגמה לאופן פעולת האלגוריתם

נמצא את מנת החלוקה ואת השארית שלה עבור חלוקת הפולינום $P(x)=x^{3}-2x^{2}-4$ (המחולק) בפולינום $D(x)=x-3,$ (המחלק).

תחילה, נכתוב מחדש את המחולק באופן הבא:

. $P(x)=x^{3}-2x^{2}+0x-4.$

כעת, נבצע את התהליך דלהלן:

נחלק את האיבר הראשון של $P(x)$ באיבר הראשון של $D(x)$ , דהיינו, את האיבר בעל החזקה המקסימלית של $P(x)$ באיבר בעל החזקה המקסימלית של $D(x)$ . במקרה זה, מדובר ב- $\left(x^{3}/x=x^{2}\right)$ . את התוצאה, נכתוב מעל לקו האופקי:

{\begin{array}{l}{\color {White}x-3)}x^{2}\\{\overline {x^{3}-2x^{2}+0x-4}}\vert {x-3}\end{array}}

נכפול את כל איברי המחלק בתוצאה שקיבלנו זה עתה, ונקבל $xD(x)=x^{2}-3x$ . נכתוב את התוצאה תחת האיברים הראשונים של המחולק:

{\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}}}\\{\underline {+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^[4], שנותר אחרי הפעולה האחרונה, הוא השארית $R(x)=5$ . לכן, קיבלנו כי $\underbrace {x^{3}-2x^{2}-4} _{P(x)}=\underbrace {(x-3)} _{D(x)}\,\underbrace {(x^{2}+x+3)} _{Q(x)}+\underbrace {5} _{R(x)}$ .

שימושים

פירוק פולינומים לגורמים

בהינתן פולינום, לעיתים, שורש אחד או יותר שלו כבר ידועים אך ייתכן כי קיימים לו כאלו נוספים. אם ידוע כי $r$ הוא שורש של פולינום $P(x)=a_{n}x^{n}+a_{n-1}x^{n-1}+...+a_{1}x+a_{0}$ - פולינום ממעלה $n$ , כלומר מתקיים כי $P(r)=a_{n}r^{n}+a_{n-1}r^{n-1}+...+a_{1}r+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_{1}x+b_{0}$ , כלומר דרגת המנה היא $n-1$ . בחלק מהמקרים, הפולינום $Q(x)=b_{n-1}x^{n-1}+b_{n-2}x^{n-2}+...+b_{1}x+b_{0}$ הוא כזה שקל יותר למצוא את שורשיו. מאחר שכל שורש שלו הוא גם שורש של $P(x)=a_{n}x^{n}+a_{n-1}x^{n-1}+...+a_{1}x+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_{n}x^{n}+a_{n-1}x^{n-1}+...+a_{1}x+a_{0}$ ונקודה $x=q$ , משוואת המשיק לגרף בנקודה $x=q$ תהיה שארית החלוקה של $f(x)$ ב- $(x-q)^{2}$ .