القاسم المشترك الأكبر لكثير الحدود

لإيجاد القاسم المشترك الأكبر لكثيرتي حدود باستخدام التحليل إلى عوامل، نحلل كلتيهما تحليلاً كاملاً. ثم نضرب جميع العوامل المشتركة. في هذه المرحلة، قد لا تكون كثيرة الحدود أحادية العامل بالضرورة، لذا نضرب الناتج في ثابت لنحصل على كثيرة حدود أحادية العامل. هذا الناتج هو القاسم المشترك الأكبر لكثيرتي الحدود، لأنه يشمل جميع القواسم المشتركة وهو أحادي العامل.

مثال واحد: أوجد القاسم المشترك الأكبر لـ x ² + 7 x + 6 و x ² − 5 x − 6 .

وبالتالي، فإن القاسم المشترك الأكبر لهما هو x + 1 .

قد يكون تحليل كثيرات الحدود صعبًا، خاصةً إذا كانت ذات درجة عالية. تُعدّ خوارزمية إقليدس طريقةً فعّالةً لأي زوج من كثيرات الحدود، حيث تستخدم القسمة الإقليدية بشكل متكرر . عند تطبيق هذه الخوارزمية على عددين، يقلّ حجم العددين في كل مرحلة. ومع كثيرات الحدود، تقلّ درجة كثيرات الحدود في كل مرحلة. أما الباقي غير الصفري الأخير، والذي يُحوّل إلى عدد أحادي إذا لزم الأمر، فهو القاسم المشترك الأكبر لكثيرتي الحدود.

وبشكل أكثر تحديدًا، لإيجاد القاسم المشترك الأكبر لكثيرتي حدود a ( x ) و b ( x ) ، يمكن افتراض أن b ≠ 0 (وإلا فإن القاسم المشترك الأكبر هو a ( x ) )، و $${\displaystyle \deg(b(x))\leq \deg(a(x))\,.}$$

تُعطي عملية القسمة الإقليدية كثيرتي حدود q ( x ) ، وهما ناتج القسمة ، و r ( x ) ، وهما الباقي ، بحيث $${\displaystyle a(x)=q_{0}(x)b(x)+r_{0}(x)\quad {\text{و}}\quad \deg(r_{0}(x))<\deg(b(x))}$$

تقسم كثيرة الحدود g ( x ) كلاً من a ( x ) و b ( x ) إذا وفقط إذا كانت تقسم كلاً _من b ( x ) و r₀ ( x ) . $${\displaystyle \gcd(a(x),b(x))=\gcd(b(x),r_{0}(x)).}$$ جلسة $${\displaystyle a_{1}(x)=b(x),b_{1}(x)=r_{0}(x),}$$ يمكن تكرار عملية القسمة الإقليدية للحصول على كثيرات حدود جديدة q₁ ( _x ) ، r₁ ( x ) ، a₂ ₍ x ) ، b₂ ₍ x ) _، وهكذا. في كل مرحلة لدينا $${\displaystyle \deg(a_{k+1})+\deg(b_{k+1})<\deg(a_{k})+\deg(b_{k}),}$$ لذا سيصل التسلسل في النهاية إلى نقطة حيث $${\displaystyle b_{N}(x)=0}$$ وقد حصل أحدهم على القاسم المشترك الأكبر: $${\displaystyle \gcd(a,b)=\gcd(a_{1},b_{1})=\cdots =\gcd(a_{N},0)=a_{N}.}$$

مثال: إيجاد القاسم المشترك الأكبر للمعادلتين x² + 7x + ⁶ و x² − ^5x − 6 :

بما أن 12 x + 12 هو آخر باقي غير صفري، فهو القاسم المشترك الأكبر لكثيرات الحدود الأصلية، والقاسم المشترك الأكبر الأحادي هو x + 1 .

في هذا المثال، من السهل تجنب إدخال المقامات عن طريق استخراج العامل المشترك 12 قبل الخطوة الثانية. يمكن دائمًا القيام بذلك باستخدام متواليات شبه الباقي ، ولكن بدون توخي الحذر، قد يؤدي ذلك إلى إدخال أعداد صحيحة كبيرة جدًا أثناء الحساب. لذلك، تُستخدم خوارزميات أخرى في الحسابات الحاسوبية، وسيتم شرحها لاحقًا.

لا تنجح هذه الطريقة إلا إذا أمكن اختبار تساوي المعاملات التي تظهر أثناء الحساب مع الصفر. لذا، عمليًا، يجب أن تكون المعاملات أعدادًا صحيحة ، أو أعدادًا نسبية ، أو عناصر من حقل منتهٍ ، أو تنتمي إلى امتداد حقل منتهٍ مولد لأحد الحقول السابقة. إذا كانت المعاملات أعدادًا عشرية تمثل أعدادًا حقيقية معروفة تقريبًا فقط، فيجب معرفة درجة القاسم المشترك الأكبر للحصول على نتيجة مستقرة عدديًا ؛ في هذه الحالة، يمكن استخدام تقنيات أخرى، تعتمد عادةً على تحليل القيم المفردة .

القسمة الإقليدية لكثيرات الحدود، المستخدمة في خوارزمية إقليدس لحساب القاسم المشترك الأكبر، تشبه إلى حد كبير القسمة الإقليدية للأعداد الصحيحة. ويستند وجودها إلى النظرية التالية: إذا كان لدينا كثيرتا حدود أحاديتان المتغير${\textstyle a}$و${\displaystyle b\neq 0}$إذا تم تعريفها على حقل ، فإنه يوجد كثيرتا حدود${\displaystyle q}$( الناتج ) و${\displaystyle r}$( الباقي ) الذي يحقق $${\displaystyle a=bq+r}$$ و $${\displaystyle \deg(r)<\deg(b),}$$ حيث تشير " deg(...) " إلى الدرجة، وتُعرَّف درجة كثير الحدود الصفري بأنها سالبة. علاوة على ذلك، يتم تحديد q و r بشكل فريد من خلال هذه العلاقات.

يختلف القسمة الإقليدية للأعداد الصحيحة عن القسمة الإقليدية في أن درجة العدد الصحيح تُستبدل بالقيمة المطلقة، وأن شرط التفرد هو افتراض أن r عدد غير سالب. تُسمى الحلقات التي تنطبق عليها هذه النظرية بالمجالات الإقليدية .

كما هو الحال مع الأعداد الصحيحة، يمكن حساب القسمة الإقليدية لكثيرات الحدود باستخدام خوارزمية القسمة المطولة . تُعرض هذه الخوارزمية عادةً للحسابات الورقية، ولكنها تعمل بكفاءة على الحواسيب عند صياغتها بالشكل التالي (لاحظ أن أسماء المتغيرات تُطابق تمامًا مناطق ورقة الحساب في القسمة المطولة الورقية). في الحساب التالي، يرمز "deg" إلى درجة المتغير (مع مراعاة أن deg(0) < 0 )، ويرمز "lc" إلى المعامل الرئيسي، وهو معامل أعلى درجة للمتغير.

التقسيم الإقليدي

المدخلات: a و b ≠ 0 كثيرتا حدود في المتغير x ؛ المخرجات: q ، ناتج القسمة، و r ، الباقي؛

يبدأ

q := 0 r := a d := deg( b ) c := lc( b ) while deg( r ) ≥ d do s := (lc( r )/ c ) ⋅ x deg( r )− d q := q + s r := r − sb end do return ( q , r )

نهاية

يعتمد برهان صحة هذه الخوارزمية على حقيقة أنه خلال حلقة "while" بأكملها، يكون لدينا a = bq + r ، ودرجة r عدد صحيح غير سالب يتناقص في كل تكرار. وبالتالي، فإن برهان صحة هذه الخوارزمية يثبت أيضًا صحة القسمة الإقليدية.

أما بالنسبة للأعداد الصحيحة، فإن القسمة الإقليدية تسمح لنا بتحديد خوارزمية إقليدس لحساب القاسم المشترك الأكبر.

انطلاقاً من كثيرتي حدود a و b ، تتكون خوارزمية إقليدس من استبدال الزوج ( a , b ) بشكل متكرر بـ ( b , rem( a , b )) (حيث يشير " rem( a , b ) " إلى باقي القسمة الإقليدية، المحسوب بواسطة خوارزمية القسم السابق)، حتى b = 0. القاسم المشترك الأكبر هو آخر باقي غير صفري.

يمكن صياغة خوارزمية إقليدس بأسلوب البرمجة التكرارية على النحو التالي: $${\displaystyle \gcd(a,b):={\begin{cases}a&{\text{if }}b=0\\\gcd(b,\operatorname {rem} (a,b))&{\text{otherwise}}.\end{cases}}}$$

في أسلوب البرمجة الإجرائية ، تصبح الخوارزمية نفسها، مع إعطاء اسم لكل باقي وسيط:

r ₀  := a r ₁  := b

for ( i  := 1; r _i ≤ 0; i  := i + 1) do

r i +1 := rem( r i −1 , r i )

نهاية التكرار

أعد r _{i -1} .

إن تسلسل درجات العدد _rᵢ متناقص تمامًا. لذا، بعد عدد لا يتجاوز deg( b ) خطوة، نحصل على باقي قسمة معدوم، ولنسمه rk _. بما أن ( a , b ) و ( b , rem( a , b )) لهما نفس القواسم، فإن مجموعة القواسم المشتركة لا تتغير بخوارزمية إقليدس، وبالتالي فإن جميع أزواج ( rᵢ _, rᵢ _{+ 1} ) لها نفس مجموعة القواسم المشتركة. إذن، القواسم المشتركة لـ a و b هي القواسم المشتركة لـ _rk⁻¹ و 0. وبالتالي، _{فإن rk⁻¹} هو القاسم المشترك الأكبر لـ a و b . هذا لا يثبت فقط أن خوارزمية إقليدس تحسب القواسم المشتركة الكبرى _، بل يثبت أيضًا وجودها.

متطابقة بيزو هي نظرية متعلقة بالقاسم المشترك الأكبر، وقد أُثبتت مبدئيًا للأعداد الصحيحة، وهي صالحة لكل مجال مثالي رئيسي . في حالة كثيرات الحدود أحادية المتغير على حقل ما، يمكن صياغتها على النحو التالي.

إذا كان g هو القاسم المشترك الأكبر لكثيرتي حدود a و b (ليس كلاهما يساوي صفرًا)، فإنه يوجد كثيرتا حدود u و v بحيث

${\displaystyle au+bv=g}$ (هوية بيزو)

و إما u = 1، v = 0 ، أو u = 0، v = 1 ، أو

$${\displaystyle \deg(u)<\deg(b)-\deg(g),\quad \deg(v)<\deg(a)-\deg(g).}$$

تكمن أهمية هذه النتيجة في حالة كثيرات الحدود في وجود خوارزمية فعّالة لحساب كثيرتي الحدود u و v . تختلف هذه الخوارزمية عن خوارزمية إقليدس بإجراء عدد أكبر من العمليات الحسابية في كل تكرار للحلقة. ولذلك تُسمى خوارزمية القاسم المشترك الأكبر الموسّعة . ومن الاختلافات الأخرى مع خوارزمية إقليدس أنها تستخدم أيضًا ناتج القسمة، المشار إليه بـ "quo"، للقسمة الإقليدية بدلًا من الباقي فقط. وتعمل هذه الخوارزمية على النحو التالي.

خوارزمية GCD الموسعة

المدخلات: أ ، ب ، كثيرات حدود أحادية المتغير

الناتج:

g ، القاسم المشترك الأكبر لـ a و b u ، v ، كما في العبارة أعلاه a 1 ، b 1 ، بحيث a = g a 1 b = g b 1

يبدأ

 ( r 0 , r 1 ) := ( a , b ) ( s 0 , s 1 ) := (1, 0) ( t 0 , t 1 ) := (0, 1) لـ ( i := 1; ri ≠ 0 ; i := i +1) نفّذ ما يلي : q := quo( ri −1 , ri ) ri +1 : =ri −1 − qri s i +1 : = s i −1 − qs i t i +1 : = t i −1 − qt i نهاية نفّذ ما يلي : g := ri −1 u := s i −1 v := t i −1 a 1 : = (−1) i −1 t i b 1 := (−1) i s i

نهاية

يعتمد إثبات أن الخوارزمية تحقق مواصفات مخرجاتها على حقيقة أنه لكل i لدينا $${\displaystyle r_{i}=as_{i}+bt_{i}}$$$${\displaystyle s_{i}t_{i+1}-t_{i}s_{i+1}=s_{i}t_{i-1}-t_{i}s_{i-1},}$$ المساواة الأخيرة تعني $${\displaystyle s_{i}t_{i+1}-t_{i}s_{i+1}=(-1)^{i}.}$$ ويستند التأكيد على الدرجات إلى حقيقة أنه في كل تكرار، تزداد درجات s _i و t _i على الأكثر مع انخفاض درجة r _{i .}

ومن السمات المثيرة للاهتمام في هذه الخوارزمية أنه عندما تكون هناك حاجة إلى معاملات هوية بيزو، يحصل المرء مجانًا على ناتج قسمة كثيرات الحدود المدخلة بواسطة قاسمها المشترك الأكبر.

في حالة كثيرات الحدود أحادية المتغير، توجد علاقة وثيقة بين القاسم المشترك الأكبر والمحصلات . وبشكل أدق، فإن محصلة كثيرتي حدود P و Q هي دالة كثيرة الحدود لمعاملات P و Q ، وتساوي صفرًا إذا وفقط إذا كان القاسم المشترك الأكبر لـ P و Q غير ثابت.

تُعد نظرية المحصلات الفرعية تعميمًا لهذه الخاصية، حيث تسمح بتوصيف القاسم المشترك الأكبر لكثيرتي حدود بشكل عام، وتكون المحصلة هي كثيرة الحدود الفرعية الصفرية. ^{[ 1 ]}

كثير الحدود الفرعي الناتج من الرتبة i ، _S _i ( P , Q ) لكثيرتي حدود P و Q، هو كثير حدود من الدرجة i على الأكثر ، ومعاملاته دوال متعددة الحدود لمعاملات P و Q. والمعامل الرئيسي الفرعي الناتج من الرتبة _i، s _i ( P , Q ) هو معامل الدرجة i من S _{_i} ( P , Q ) . وتتميز هذه كثيرات الحدود بخاصية أن القاسم المشترك الأكبر لـ P و Q له درجة d إذا وفقط إذا $${\displaystyle s_{0}(P,Q)=\cdots =s_{d-1}(P,Q)=0,\ s_{d}(P,Q)\neq 0.}$$

في هذه الحالة، S _d ( P , Q ) هو القاسم المشترك الأكبر لـ P و Q و $${\displaystyle S_{0}(P,Q)=\cdots =S_{d-1}(P,Q)=0.}$$

يُعرَّف كل معامل من معاملات كثيرات الحدود الناتجة جزئيًا على أنه محدد مصفوفة فرعية من مصفوفة سيلفستر لـ P و Q. وهذا يعني أن كثيرات الحدود الناتجة جزئيًا "تتخصص" جيدًا. وبشكل أدق، تُعرَّف كثيرات الحدود الناتجة جزئيًا لكثيرات الحدود على أي حلقة تبديلية R ، ولها الخاصية التالية.

ليكن φ تشاكلًا حلقيًا من R إلى حلقة تبديلية أخرى S. يمتد هذا التشاكل إلى تشاكل آخر، يُرمز إليه أيضًا بـ φ، بين حلقتي كثيرات الحدود على R و S. عندئذٍ، إذا كانت P و Q كثيرتي حدود أحاديتي المتغير بمعاملات في R بحيث $${\displaystyle \deg(P)=\deg(\varphi (P))}$$ و $${\displaystyle \deg(Q)=\deg(\varphi (Q)),}$$ثم فإن كثيرات الحدود الناتجة الفرعية ومعاملات الناتج الفرعي الرئيسية لـ φ ( P ) و φ ( Q ) هي صورة φ لتلك الخاصة بـ P و Q.

تتمتع المحصلات الفرعية بخاصيتين مهمتين تجعلانها أساسية لحساب القاسم المشترك الأكبر لكثيرتي حدود بمعاملات صحيحة على الحواسيب. أولًا، يسمح تعريفها من خلال المحددات بتحديد حجم معاملات القاسم المشترك الأكبر باستخدام متباينة هادامارد . ثانيًا، يسمح هذا الحد وخاصية التخصيص الجيد بحساب القاسم المشترك الأكبر لكثيرتي حدود بمعاملات صحيحة من خلال الحساب النمطي ونظرية الباقي الصينية (انظر أدناه ).

محتوى كثير الحدود p ∈ R [ X ] ، ويرمز له بـ " cont( p ) "، هو القاسم المشترك الأكبر لمعاملاته. ويمكن كتابة كثير الحدود q ∈ F [ X ] على النحو التالي:$${\displaystyle q={\frac {p}{c}}}$$ حيث p ∈ R [ X ] و c ∈ R : يكفي أن نأخذ c مضاعفًا لجميع مقامات معاملات q ( على سبيل المثال، حاصل ضربها) و p = cq . يُعرَّف محتوى q على النحو التالي:$${\displaystyle \operatorname {cont} (q)={\frac {\operatorname {cont} (p)}{c}}.}$$في كلتا الحالتين ، يتم تحديد المحتوى حتى الضرب بوحدة من R.

يُعرَّف الجزء الأولي لكثير الحدود في R [ X ] أو F [ X ] بواسطة$${\displaystyle \operatorname {primpart} (p)={\frac {p}{\operatorname {cont} (p)}}.}$$

في كلتا الحالتين، يكون متعدد الحدود في R [ X ] بدائيًا ، مما يعني أن 1 هو القاسم المشترك الأكبر لمعاملاته.

وبالتالي، يمكن تحليل كل متعددة حدود في R [ X ] أو F [ X ] إلى عواملها الأولية.$${\displaystyle p=\operatorname {cont} (p)\,\operatorname {primpart} (p),}$$ وهذا التحليل فريد حتى ضرب المحتوى بوحدة من R وضرب الجزء الأولي بمعكوس هذه الوحدة.

تُشير مبرهنة غاوس إلى أن حاصل ضرب كثيرتي حدود بدائيتين هو كثير حدود بدائي. ويترتب على ذلك أن $${\displaystyle \operatorname {primpart} (pq)=\operatorname {primpart} (p)\operatorname {primpart} (q)}$$ و $${\displaystyle \operatorname {cont} (pq)=\operatorname {cont} (p)\operatorname {cont} (q).}$$

تشير العلاقات الواردة في القسم السابق إلى وجود علاقة قوية بين القاسم المشترك الأكبر في R [ X ] وفي F [ X ] . ولتجنب أي لبس، سيتم فهرسة الرمز " gcd " فيما يلي بواسطة الحلقة التي يُحسب فيها القاسم المشترك الأكبر.

إذا كان _q1 و q2 ينتميان _إلى F [ X ] ، فإن $${\displaystyle \operatorname {primpart} (\gcd _{F[X]}(q_{1},q_{2}))=\gcd _{R[X]}(\operatorname {primpart} (q_{1}),\operatorname {primpart} (q_{2})).}$$

إذا كان _p1 و p2 ينتميان إلى R [ X _] ، فإن $${\displaystyle \gcd _{R[X]}(p_{1},p_{2})=\gcd _{R}(\operatorname {cont} (p_{1}),\operatorname {cont} (p_{2}))\gcd _{R[X]}(\operatorname {primpart} (p_{1}),\operatorname {primpart} (p_{2})),}$$ و $${\displaystyle \gcd _{R[X]}(\operatorname {primpart} (p_{1}),\operatorname {primpart} (p_{2}))=\operatorname {primpart} (\gcd _{F[X]}(p_{1},p_{2})).}$$

وبالتالي فإن حساب القاسم المشترك الأكبر لكثيرات الحدود هو في الأساس نفس المشكلة على F [ X ] وعلى R [ X ] .

بالنسبة لكثيرات الحدود أحادية المتغير على الأعداد النسبية، قد يظن المرء أن خوارزمية إقليدس طريقة ملائمة لحساب القاسم المشترك الأكبر. إلا أنها تتضمن تبسيط عدد كبير من كسور الأعداد الصحيحة، مما يجعل الخوارزمية الناتجة غير فعالة. لهذا السبب، صُممت طرق لتعديل خوارزمية إقليدس للعمل فقط مع كثيرات الحدود على الأعداد الصحيحة. وتتمثل هذه الطرق في استبدال القسمة الإقليدية، التي تُدخل الكسور، بما يُسمى القسمة الزائفة ، واستبدال متتالية الباقي في خوارزمية إقليدس بما يُسمى متتاليات الباقي الزائفة (انظر أدناه ).

في القسم السابق، رأينا أنه يمكن استنتاج القاسم المشترك الأكبر لكثيرات الحدود في R [ X ] من القواسم المشتركة الأكبر في R و F [ X ] . وبالنظر إلى البرهان، يتضح أن هذا يسمح لنا بإثبات وجود القواسم المشتركة الأكبر في R [ X ] ، إذا كانت موجودة في R و F [ X ] . وبالتحديد، إذا كانت القواسم المشتركة الأكبر موجودة في R ، وإذا اختُزلت X إلى متغير واحد، فإن هذا يثبت وجود القواسم المشتركة الأكبر في R [ X ] (وتثبت خوارزمية إقليدس وجود القواسم المشتركة الأكبر في F [ X ] ).

يمكن اعتبار متعددة الحدود في n متغيرًا متعددة حدود أحادية المتغير على حلقة متعددات الحدود في ( n - 1 ) متغيرًا. وبالتالي، يُبين الاستدلال التكراري على عدد المتغيرات أنه إذا وُجدت القواسم المشتركة الكبرى (GCDs) ويمكن حسابها في R ، فإنها موجودة ويمكن حسابها في أي حلقة متعددة الحدود متعددة المتغيرات على R. على وجه الخصوص، إذا كانت R إما حلقة الأعداد الصحيحة أو حقلًا، فإن القواسم المشتركة الكبرى موجودة في R [ x1 _, ..., xn _] ، وما سبق يُقدم خوارزمية لحسابها.

إن البرهان على أن حلقة متعددة الحدود فوق مجال تحليل فريد هي أيضًا مجال تحليل فريد مشابه، ولكنه لا يقدم خوارزمية، لأنه لا توجد خوارزمية عامة لتحليل كثيرات الحدود أحادية المتغير فوق حقل (هناك أمثلة على الحقول التي لا توجد لها أي خوارزمية تحليل لكثيرات الحدود أحادية المتغير).

The simplest (to define) remainder sequence consists in taking always α = 1. In practice, it is not interesting, as the size of the coefficients grows exponentially with the degree of the input polynomials. This appears clearly on the example of the preceding section, for which the successive pseudo-remainders are $${\displaystyle -15\,X^{4}+3\,X^{2}-9,}$$$${\displaystyle 15795\,X^{2}+30375\,X-59535,}$$$${\displaystyle 1254542875143750\,X-1654608338437500,}$$$${\displaystyle 12593338795500743100931141992187500.}$$ The number of digits of the coefficients of the successive remainders is more than doubled at each iteration of the algorithm. This is typical behavior of the trivial pseudo-remainder sequences.

The primitive pseudo-remainder sequence consists in taking for α the content of the numerator. Thus all the r_i are primitive polynomials.

The primitive pseudo-remainder sequence is the pseudo-remainder sequence, which generates the smallest coefficients. However it requires to compute a number of GCD's in Z, and therefore is not sufficiently efficient to be used in practice, especially when Z is itself a polynomial ring.

With the same input as in the preceding sections, the successive remainders, after division by their content are $${\displaystyle -5\,X^{4}+X^{2}-3,}$$$${\displaystyle 13\,X^{2}+25\,X-49,}$$$${\displaystyle 4663\,X-6150,}$$$${\displaystyle 1.}$$ The small size of the coefficients hides the fact that a number of integers GCD and divisions by the GCD have been computed.

يمكن أيضًا حساب متتالية المحصلات الفرعية باستخدام البواقي الزائفة. وتتلخص العملية في اختيار قيمة α بحيث يكون كل rᵢ متعدد حدود محصلة فرعية. ومن المثير للدهشة أن حساب α سهل للغاية (انظر أدناه). من ناحية أخرى، يُعد إثبات صحة الخوارزمية أمرًا صعبًا، لأنه يجب _أن يأخذ في الاعتبار جميع احتمالات الفرق في درجات باقيين متتاليين.

نادراً ما تكون معاملات المتتالية الناتجة الفرعية أكبر بكثير من معاملات متتالية الباقي الزائفة الأولية. ولأن حسابات القاسم المشترك الأكبر في Z غير مطلوبة، فإن المتتالية الناتجة الفرعية مع البواقي الزائفة تُعطي الحساب الأكثر كفاءة.

باستخدام نفس المدخلات كما في الأقسام السابقة، تكون البواقي المتتالية هي $${\displaystyle 15\,X^{4}-3\,X^{2}+9,}$$$${\displaystyle 65\,X^{2}+125\,X-245,}$$$${\displaystyle 9326\,X-12300,}$$$${\displaystyle 260708.}$$ تتميز المعاملات بحجم معقول، ويتم الحصول عليها دون الحاجة إلى حساب القاسم المشترك الأكبر، بل فقط من خلال عمليات القسمة الدقيقة. وهذا ما يجعل هذه الخوارزمية أكثر كفاءة من خوارزميات متواليات الباقي الزائفة الأولية.

تُعرض أدناه خوارزمية حساب متتالية النتائج الفرعية ذات البواقي الزائفة. في هذه الخوارزمية، يكون المدخل ( a , b ) زوجًا من كثيرات الحدود في Z [ X ] . تمثل ri _{البواقي} الزائفة المتتالية في Z [ X ] ، والمتغيران i و di عددان صحيحان غير سالبين، وترمز الأحرف اليونانية إلى عناصر في Z.deg() تُشير الدالتان _إلىrem() درجة كثيرة الحدود وباقي القسمة الإقليدية. في الخوارزمية، يكون هذا الباقي دائمًا في Z [ X ] . أخيرًا ، تكون عمليات القسمة التي يُرمز لها بـ / دائمًا تامة، ويكون ناتجها إما في Z [ X ] أو في Z.

r ₀  := a r ₁  := b for ( i  := 1; r _i ≠ 0; i  := i +1) do

d i := deg( r i −1 ) − deg( r i ) γ i := lc( r i ) إذا كان i = 1 فإن β 1 := (−1) d 1 +1 ψ 1 := −1 وإلا فإن ψ i := (− γ i −1 ) d i −1 / ψ i −1 d i −1 −1 β i := − γ i −1 ψ i d i نهاية الشرط r i +1 := rem( γ i d i +1 r i −1 , r i ) / β i

نهاية لـ

ملاحظة: "lc" تعني المعامل الرئيسي، وهو معامل أعلى درجة للمتغير.

لا تحسب هذه الخوارزمية القاسم المشترك الأكبر (آخر عدد غير صفري rᵢ ) فحسب ، بل تحسب أيضًا جميع كثيرات الحدود الناتجة: الباقي rᵢ هو كثيرة الحدود الناتجة من الدرجة (deg( rᵢ - 1 ) - 1) . إذا كانت deg( rᵢ ) < deg( rᵢ - 1 ) - 1 ، فإن كثيرة الحدود الناتجة من الدرجة deg( rᵢ ) هي lc( rᵢ ) deg( rᵢ - 1 ) - deg ( rᵢ ) - 1 rᵢ . جميع كثيرات الحدود الناتجة الأخرى تساوي صفرًا .

يمكن استخدام البواقي الزائفة لإنشاء متتابعات لها نفس خصائص متتابعات ستورم . يتطلب ذلك التحكم في إشارات البواقي الزائفة المتتالية، بحيث تكون لها نفس إشارات متتابعة ستورم. ويمكن تحقيق ذلك بتعريف باقي زائف مُعدَّل كما يلي.

لو${\displaystyle \deg(A)=a}$و${\displaystyle \deg(B)=b}$و a ≥ b ، فإن الباقي الزائف المعدل prem2( A , B ) للقسمة الزائفة لـ A على B هو $${\displaystyle \operatorname {prem2} (A,B)=-\operatorname {rem} (\left|\operatorname {lc} (B)\right|^{a-b+1}A,B),}$$ حيث | lc( B ) | هي القيمة المطلقة للمعامل الرئيسي لـ B (معامل X ^b ).

بالنسبة لكثيرات الحدود المدخلة ذات المعاملات الصحيحة، يسمح هذا باسترجاع متواليات ستورم المكونة من كثيرات حدود ذات معاملات صحيحة. ويمكن تعديل متوالية الباقي الزائفة الناتجة بشكل مماثل، وفي هذه الحالة تتطابق إشارات البواقي مع تلك المحسوبة على الأعداد النسبية.

لاحظ أن الخوارزمية المستخدمة لحساب متتالية الباقي الزائف الفرعية المذكورة أعلاه ستحسب كثيرات حدود فرعية خاطئة إذا استخدمنا${\displaystyle -\mathrm {prem2} (A,B)}$بدلاً من${\displaystyle \operatorname {prem} (A,B)}$.