חלוקת פולינומים – הבדלי גרסאות

מ (הוספת קטגוריה:אלגוריתמים באמצעות HotCat)
האלגוריתם מיישם הלכה למעשה את תכונת הפולינומים הבאה. בהינתן <math>P(x)=a_nx^n+a_{n-1}x^{n-1}+...+a_1x+a_0</math> (מחולק) ו-<math>D(x)=b_kx^k+b_{k-1}x^{k-1}+...+b_1x+b_0</math> (מחלק) כך ש-<math>k\le n</math> ובניסוח מדויק, <math>\deg(D(x))\le\deg(P(x))</math>, ניתן לבטא את <math>P(x)</math> כ-<math>P(x)=D(x)Q(x)+R(x)</math> עבור <math>Q(x)</math> פולינום שיקרא המנה ועבור <math>R(x)</math> פולינום שיקרא שארית החלוקה, כך שדרגת השארית <math>R(x)</math> קטנה (ממש) מדרגת המחלק <math>D(x)</math>, כלומר <math>\deg(R(x))<\deg(D(x))</math>.
 
התוצאה <math>R(x)=0</math> תופיע [[אם ורק אם]] <math>D(x)</math> הוא גורם של <math>P(x)</math>, כלומר, ניתן לרשום את <math>P(x)</math> כמכפלה של הפולינום <math>D(x)</math> בפולינום אחר. בנוסף, על פי [[המשפט הקטן של בזו]], אם <math>a</math> הוא שורש של <math>P(x)</math>, דהיינו <math>P(a)=0</math>, אזי <math>(x-a)</math> הוא גורם של <math>P(x)</math>. לכן, נעשה שימוש נרחב בחלוקת פולינומים הן על מנת לפרק את הפולינום לגורמים והן על מנת לפשט את הליך מציאת השורשים הנוספים שלו, אם אחד מהם כבר ידוע{{הערה|https://math-wiki.com/images/1/12/חילוק_פולינומים_הסבר.PDF}}.
 
==דוגמה==