बहुपद महत्तम सामान्य भाजक

बीजगणित में, दो बहुपदों का सबसे बड़ा आम भाजक (अक्सर जीसीडी के रूप में संक्षिप्त) उच्चतम संभव डिग्री का एक बहुपद है, जो दोनों मूल बहुपदों का गुणनखंड है। यह अवधारणा दो पूर्णांकों के सबसे बड़े सामान्य विभाजक के अनुरूप है।

एक क्षेत्र (गणित) पर अविभाजित बहुपदों के महत्वपूर्ण मामले में बहुपद GCD की गणना की जा सकती है, जैसे पूर्णांक GCD के लिए, बहुपद लंबे विभाजन का उपयोग करके यूक्लिडियन एल्गोरिथ्म द्वारा। बहुपद GCD को केवल व्युत्क्रमणीय स्थिरांक से गुणन तक ही परिभाषित किया जाता है।

पूर्णांक जीसीडी और बहुपद जीसीडी के बीच समानता यूक्लिडियन एल्गोरिथ्म और यूक्लिडियन विभाजन से निकाले जा सकने वाले सभी गुणों को एकतरफा बहुपदों तक विस्तारित करने की अनुमति देती है। इसके अलावा, बहुपद जीसीडी में विशिष्ट गुण हैं जो इसे बीजगणित के विभिन्न क्षेत्रों में एक मौलिक धारणा बनाते हैं। आमतौर पर, दो बहुपदों के जीसीडी के कार्यों की जड़ दो बहुपदों की आम जड़ें होती हैं, और यह जड़ों पर उन्हें गणना किए बिना जानकारी प्रदान करती है। उदाहरण के लिए, एक बहुपद की कई जड़ें बहुपद और उसके व्युत्पन्न की जीसीडी की जड़ें हैं, और आगे की जीसीडी संगणनाएं बहुपद के वर्ग-मुक्त गुणन की गणना करने की अनुमति देती हैं, जो बहुपद प्रदान करती हैं जिनकी जड़ें दी गई बहुलता की जड़ें हैं ( गणित) मूल बहुपद का।

सबसे बड़ा सामान्य विभाजक परिभाषित किया जा सकता है और मौजूद है, अधिक आम तौर पर, एक क्षेत्र या पूर्णांक की अंगूठी पर बहुभिन्नरूपी बहुपदों के लिए, और एक अद्वितीय गुणनखंड डोमेन पर भी। गुणांकों के घेरे में जैसे ही किसी के पास GCD एल्गोरिथम होता है, उनकी गणना करने के लिए एल्गोरिदम मौजूद होते हैं। यूक्लिडियन एल्गोरिथ्म के एक संस्करण के लिए समस्या को कम करने के लिए ये एल्गोरिदम चर की संख्या पर एक पुनरावृत्ति द्वारा आगे बढ़ते हैं। वे कंप्यूटर बीजगणित में एक मौलिक उपकरण हैं, क्योंकि कंप्यूटर बीजगणित प्रणालियां भिन्नों को सरल बनाने के लिए उन्हें व्यवस्थित रूप से उपयोग करती हैं। इसके विपरीत, कंप्यूटर बीजगणित प्रणालियों की दक्षता की आवश्यकता को पूरा करने के लिए बहुपद जीसीडी के अधिकांश आधुनिक सिद्धांत विकसित किए गए हैं।

सामान्य परिभाषा

होने देना p और q अभिन्न डोमेन में गुणांक वाले बहुपद हों F, आमतौर पर एक क्षेत्र (गणित) या पूर्णांक। का सबसे बड़ा सामान्य विभाजक p और q एक बहुपद है d जो विभाजित करता है p और q, और ऐसा कि हर आम विभाजक p और q भी बांटता है d. बहुपदों की प्रत्येक जोड़ी (दोनों शून्य नहीं) में GCD होती है यदि और केवल यदि F एक अद्वितीय कारककरण डोमेन है।

अगर F एक क्षेत्र है और p और q दोनों शून्य नहीं हैं, एक बहुपद हैं d महानतम समापवर्तक है यदि और केवल यदि यह दोनों को विभाजित करता है p और q, और यह इस संपत्ति वाले बहुपदों में सबसे बड़ी डिग्री है। अगर p = q = 0, GCD 0 है। हालांकि, कुछ लेखकों का मानना ​​है कि यह इस मामले में परिभाषित नहीं है।

का सबसे बड़ा सामान्य विभाजक p और q आमतौर पर निरूपित किया जाता हैgcd(p, q) .

महत्तम समापवर्तक अद्वितीय नहीं है: यदि d का GCD है p और q, फिर बहुपद f एक और GCD है अगर और केवल अगर कोई व्युत्क्रमणीय तत्व है u का F ऐसा है कि

$f=ud$

और

$d=u^{-1}f$.

दूसरे शब्दों में, GCD एक व्युत्क्रमणीय स्थिरांक द्वारा गुणा करने के लिए अद्वितीय है।

पूर्णांकों के मामले में, इस अनिश्चितता को जीसीडी के रूप में चुनकर तय किया गया है, अद्वितीय जो सकारात्मक है (एक और है, जो इसके विपरीत है)। इस परिपाटी के साथ, दो पूर्णांकों का GCD भी सबसे बड़ा (सामान्य क्रम के लिए) सामान्य विभाजक है। हालांकि, चूंकि एक अभिन्न डोमेन पर बहुपदों के लिए कोई प्राकृतिक कुल क्रम नहीं है, इसलिए यहां उसी तरह आगे नहीं बढ़ सकता है। एक क्षेत्र पर एकतरफा बहुपदों के लिए, जीसीडी को मोनिक बहुपद होने की आवश्यकता हो सकती है (अर्थात इसके उच्चतम डिग्री के गुणांक के रूप में 1 है), लेकिन अधिक सामान्य मामलों में कोई सामान्य सम्मेलन नहीं है। इसलिए, समानता पसंद है d = gcd(p, q) या gcd(p, q) = gcd(r, s) अंकन के सामान्य दुरुपयोग हैं जिन्हें पढ़ा जाना चाहिएd का GCD है p और q औरp और q के पास GCD का समान सेट है r और s . विशेष रूप से, gcd(p, q) = 1 का अर्थ है कि व्युत्क्रमणीय स्थिरांक केवल सामान्य विभाजक हैं। इस मामले में, पूर्णांक मामले के अनुरूप, कोई कहता है कि p और q हैंcoprime polynomials.

गुण

• जैसा कि ऊपर कहा गया है, दो बहुपदों का जीसीडी मौजूद है यदि गुणांक या तो एक क्षेत्र से संबंधित हैं, पूर्णांक की अंगूठी, या अधिक आम तौर पर एक अद्वितीय कारककरण डोमेन के लिए।
• अगर c का कोई सामान्य विभाजक है p और q, तब c उनके GCD को विभाजित करता है।
• $\gcd(p,q)=\gcd(q,p).$
• $\gcd(p,q)=\gcd(q,p+rq)$ किसी भी बहुपद के लिए r. यह संपत्ति यूक्लिडियन एल्गोरिथम के प्रमाण के आधार पर है।
• किसी भी उलटे तत्व के लिए k गुणांक की अंगूठी की, $\gcd(p,q)=\gcd(p,kq)$.
• इस तरह $\gcd(p,q)=\gcd(a_{1}p+b_{1}q,a_{2}p+b_{2}q)$ किसी भी स्केलर के लिए $a_{1},b_{1},a_{2},b_{2}$ ऐसा है कि $a_{1}b_{2}-a_{2}b_{1}$ उलटा है।
• अगर $\gcd(p,r)=1$, तब $\gcd(p,q)=\gcd(p,qr)$.
• अगर $\gcd(q,r)=1$, तब $\gcd(p,qr)=\gcd(p,q)\,\gcd(p,r)$.
• दो अविभाज्य बहुपदों के लिए p और q एक क्षेत्र में, वहाँ बहुपद मौजूद हैं a और b, ऐसा है कि $\gcd(p,q)=ap+bq$ और $\gcd(p,q)$ के ऐसे प्रत्येक रैखिक संयोजन को विभाजित करता है p और q (बेज़ाउट की पहचान)।
• तीन या अधिक बहुपदों के महत्तम समापवर्तक को दो बहुपदों के समान परिभाषित किया जा सकता है। पहचान द्वारा दो बहुपदों के जीसीडी से पुनरावर्ती रूप से इसकी गणना की जा सकती है:

$\gcd(p,q,r)=\gcd(p,\gcd(q,r)),$

और

$\gcd(p_{1},p_{2},\dots ,p_{n})=\gcd(p_{1},\gcd(p_{2},\dots ,p_{n})).$

जीसीडी हाथ से संगणना द्वारा

दो बहुपदों का महत्तम समापवर्तक ज्ञात करने के कई तरीके हैं। उनमें से दो हैं:

1. बहुपदों का गुणनखंडन, जिसमें व्यक्ति प्रत्येक व्यंजक के गुणनखंडों का पता लगाता है, फिर गुणनखंडों के प्रत्येक समुच्चय में से सभी के द्वारा रखे गए सामान्य गुणनखंडों के समुच्चय का चयन करता है। यह विधि केवल साधारण मामलों में उपयोगी हो सकती है, क्योंकि गुणनखंडन आमतौर पर सबसे बड़े सामान्य विभाजक की गणना करने से अधिक कठिन होता है।
2. यूक्लिडियन एल्गोरिथ्म, जिसका उपयोग दो बहुपदों के GCD को उसी तरह से खोजने के लिए किया जा सकता है जैसे दो संख्याओं के लिए किया जाता है।

फैक्टरिंग

गुणनखंडन का उपयोग करके दो बहुपदों का GCD ज्ञात करने के लिए, बस दो बहुपदों को पूरी तरह से गुणनखंडित करें। फिर, सभी सामान्य कारकों का उत्पाद लें। इस स्तर पर, हमारे पास अनिवार्य रूप से एक मोनिक बहुपद नहीं है, इसलिए अंत में इसे एक अचर से गुणा करके इसे एक मोनिक बहुपद बना दें। यह दो बहुपदों का GCD होगा क्योंकि इसमें सभी सामान्य विभाजक शामिल हैं और यह एकात्मक है।

उदाहरण एक: का GCD ज्ञात करें x² + 7x + 6 और x² − 5x − 6.

x² + 7x + 6 = (x + 1)(x + 6)

x² − 5x − 6 = (x + 1)(x − 6)

इस प्रकार, उनका GCD है x + 1.

यूक्लिडियन एल्गोरिथम

बहुपदों का गुणनखण्ड करना कठिन हो सकता है, विशेषकर यदि बहुपदों की कोटि बड़ी हो। यूक्लिडियन एल्गोरिथम एक ऐसी विधि है जो बहुपदों की किसी भी जोड़ी के लिए काम करती है। यह यूक्लिडियन डिवीजन का बार-बार उपयोग करता है। इस एल्गोरिथ्म का उपयोग दो संख्याओं पर करते समय, प्रत्येक चरण में संख्याओं का आकार घटता है। बहुपद के साथ, बहुपद की डिग्री प्रत्येक चरण में घट जाती है। अंतिम अशून्य शेषफल, यदि आवश्यक हो तो मोनिक बहुपद बनाया गया है, दो बहुपदों का GCD है।

अधिक विशेष रूप से, दो बहुपदों की जीसीडी खोजने के लिए a(x) और b(x), कोई मान सकता है b ≠ 0 (अन्यथा, जीसीडी है a(x)), और

$\deg(b(x))\leq \deg(a(x))\,.$

यूक्लिडियन विभाजन दो बहुपद प्रदान करता है q(x), भागफल और r(x), शेष ऐसे कि

$a(x)=q_{0}(x)b(x)+r_{0}(x)\qquad {\text{and}}\qquad \deg(r_{0}(x))<\deg(b(x))$

एक बहुपद g(x) दोनों को विभाजित करता है a(x) और b(x) अगर और केवल अगर यह दोनों को विभाजित करता है b(x) और r₀(x). इस प्रकार

$\gcd(a(x),b(x))=\gcd(b(x),r_{0}(x)).$

सेटिंग

$a_{1}(x)=b(x),b_{1}(x)=r_{0}(x),$

कोई नया बहुपद प्राप्त करने के लिए यूक्लिडियन विभाजन को दोहरा सकता है q₁(x), r₁(x), a₂(x), b₂(x) और इसी तरह। हमारे पास प्रत्येक चरण में है

$\deg(a_{k+1})+\deg(b_{k+1})<\deg(a_{k})+\deg(b_{k}),$

तो अनुक्रम अंततः उस बिंदु पर पहुंच जाएगा जिस पर

$b_{N}(x)=0$

और एक को जीसीडी मिला है:

$\gcd(a,b)=\gcd(a_{1},b_{1})=\cdots =\gcd(a_{N},0)=a_{N}.$

उदाहरण: की GCD ढूँढना x² + 7x + 6 और x² − 5x − 6:

x² + 7x + 6 = 1 ⋅ (x² − 5x − 6) + (12 x + 12)

x² − 5x − 6 = (12 x + 12) (1/12 x − 1/2) + 0

तब से 12 x + 12 अंतिम अशून्य शेषफल है, यह मूल बहुपदों का GCD है, और मोनिक बहुपद GCD है x + 1.

इस उदाहरण में, दूसरे चरण से पहले 12 को गुणनखंड करके हर का परिचय देने से बचना मुश्किल नहीं है। यह हमेशा #छद्म-शेष अनुक्रमों|छद्म-शेष अनुक्रमों का उपयोग करके किया जा सकता है, लेकिन, ध्यान दिए बिना, यह गणना के दौरान बहुत बड़े पूर्णांक प्रस्तुत कर सकता है। इसलिए, कंप्यूटर संगणना के लिए, अन्य एल्गोरिदम का उपयोग किया जाता है, जिनका वर्णन नीचे किया गया है।

यह विधि तभी काम करती है जब कोई गणना के दौरान होने वाले गुणांकों के शून्य की समानता का परीक्षण कर सकता है। इसलिए, व्यवहार में, गुणांक पूर्णांक, परिमेय संख्या, परिमित क्षेत्र के तत्व होने चाहिए, या पूर्ववर्ती क्षेत्रों में से किसी एक के कुछ सूक्ष्म रूप से उत्पन्न क्षेत्र विस्तार से संबंधित होने चाहिए। यदि गुणांक फ़्लोटिंग-पॉइंट संख्याएँ हैं जो वास्तविक संख्याओं का प्रतिनिधित्व करती हैं जो केवल लगभग ज्ञात हैं, तो किसी को एक अच्छी तरह से परिभाषित संगणना परिणाम के लिए GCD की डिग्री पता होनी चाहिए (जो एक संख्यात्मक रूप से स्थिर परिणाम है; इस मामले में अन्य तकनीकों का उपयोग किया जा सकता है) , आमतौर पर एकवचन मूल्य अपघटन पर आधारित होता है।

एक क्षेत्र में गुणांक वाले बहुपद बहुपद

एक क्षेत्र पर एकविभिन्न बहुपदों का मामला कई कारणों से विशेष रूप से महत्वपूर्ण है। सबसे पहले, यह सबसे प्रारंभिक मामला है और इसलिए बीजगणित के अधिकांश पहले पाठ्यक्रमों में दिखाई देता है। दूसरे, यह पूर्णांकों के मामले के समान है, और यह सादृश्य यूक्लिडियन डोमेन की धारणा का स्रोत है। एक तीसरा कारण यह है कि बहुभिन्नरूपी बहुपद मामले के लिए सिद्धांत और एल्गोरिदम और एक अद्वितीय गुणनखंड डोमेन में गुणांक के लिए इस विशेष मामले पर दृढ़ता से आधारित हैं। अंतिम लेकिन कम नहीं, बहुपद GCD एल्गोरिदम और व्युत्पन्न एल्गोरिदम किसी को गणना किए बिना बहुपद की जड़ों पर उपयोगी जानकारी प्राप्त करने की अनुमति देते हैं।

यूक्लिडियन विभाजन

बहुपदों का यूक्लिडियन विभाजन, जिसका उपयोग #यूक्लिड के एल्गोरिथ्म|यूक्लिड के एल्गोरिदम में जीसीडी की गणना के लिए किया जाता है, पूर्णांकों के यूक्लिडियन विभाजन के समान है। इसका अस्तित्व निम्नलिखित प्रमेय पर आधारित है: दो अविभाजित बहुपदों a और b ≠ 0 को एक क्षेत्र पर परिभाषित किया गया है, वहां दो बहुपद q (भागफल) और r (शेष) मौजूद हैं जो संतुष्ट करते हैं

$a=bq+r$

और

$\deg(r)<\deg(b),$

जहाँ deg(...) डिग्री को दर्शाता है और शून्य बहुपद की डिग्री को ऋणात्मक के रूप में परिभाषित किया जाता है। इसके अलावा, क्यू और आर विशिष्ट रूप से इन संबंधों द्वारा परिभाषित हैं।

पूर्णांकों के यूक्लिडियन विभाजन से अंतर यह है कि, पूर्णांकों के लिए, डिग्री को निरपेक्ष मान से बदल दिया जाता है, और अद्वितीयता रखने के लिए किसी को यह मान लेना चाहिए कि r गैर-ऋणात्मक है। वे वलय जिनके लिए ऐसा प्रमेय मौजूद है, यूक्लिडियन डोमेन कहलाते हैं।

पूर्णांकों की तरह, बहुपदों के यूक्लिडियन विभाजन की गणना बहुपद दीर्घ विभाजन एल्गोरिथम द्वारा की जा सकती है। यह एल्गोरिदम आमतौर पर पेपर-एंड-पेंसिल गणना के लिए प्रस्तुत किया जाता है, लेकिन यह कंप्यूटर पर अच्छी तरह से काम करता है जब निम्नानुसार औपचारिक रूप दिया जाता है (ध्यान दें कि चर के नाम पेंसिल-एंड-पेपर गणना में पेपर शीट के क्षेत्रों से बिल्कुल मेल खाते हैं) विभाजन)। निम्नलिखित संगणना में deg इसके तर्क की डिग्री के लिए खड़ा है (सम्मेलन के साथ deg(0) < 0), और एलसी प्रमुख गुणांक के लिए खड़ा है, चर की उच्चतम डिग्री का गुणांक।

Euclidean division

Input: a and b ≠ 0 two polynomials in the variable x;
Output: q, the quotient, and r, the remainder;

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

इस एल्गोरिथ्म की वैधता का प्रमाण इस तथ्य पर निर्भर करता है कि पूरे लूप के दौरान, हमारे पास है a = bq + r और deg(r) एक गैर-ऋणात्मक पूर्णांक है जो प्रत्येक पुनरावृत्ति पर घटता है। इस प्रकार इस एल्गोरिथम की वैधता का प्रमाण यूक्लिडियन डिवीजन की वैधता को भी प्रमाणित करता है।

यूक्लिड का एल्गोरिथ्म

पूर्णांकों के लिए, यूक्लिडियन डिवीजन हमें GCDs की गणना के लिए यूक्लिड के एल्गोरिथ्म को परिभाषित करने की अनुमति देता है।

दो बहुपदों a और b से शुरू करते हुए, यूक्लिड के एल्गोरिथ्म में जोड़ी को पुनरावर्ती रूप से बदलना शामिल है (a, b) द्वारा (b, rem(a, b)) (कहाँrem(a, b) यूक्लिडियन डिवीजन के शेष भाग को दर्शाता है, जिसकी गणना पूर्ववर्ती खंड के एल्गोरिथ्म द्वारा की जाती है), जब तक कि b = 0 न हो। GCD अंतिम गैर शून्य शेष है।

यूक्लिड के एल्गोरिथ्म को पुनरावर्ती प्रोग्रामिंग शैली में औपचारिक रूप दिया जा सकता है:

$\gcd(a,b):={\text{if }}b=0{\text{ then }}a{\text{ else }}\gcd(b,\operatorname {rem} (a,b)).$

अनिवार्य प्रोग्रामिंग शैली में, एक ही एल्गोरिथ्म बन जाता है, प्रत्येक मध्यवर्ती शेष को एक नाम देता है:

${\begin{aligned}r_{0}:=a\\r_{1}:=b\end{aligned}}$

for ($i:=1$; $r_{i}\neq 0$; $i:=i+1$) do
    ${\begin{aligned}r_{i+1}&:=\operatorname {rem} (r_{i-1},r_{i})\end{aligned}}$
end do

return $(r_{i-1}).$

की डिग्रियों का क्रम r_i सख्ती से घट रहा है। इस प्रकार बाद में, अधिक से अधिक, deg(b) कदम, एक शून्य शेष मिलता है, कहते हैं r_k. जैसा (a, b) और (b, rem(a,b)) में समान विभाजक हैं, यूक्लिड के एल्गोरिथ्म द्वारा सामान्य विभाजकों का सेट नहीं बदला जाता है और इस प्रकार सभी जोड़े (r_i, r_i+1) के समान भाजक हैं। के सामान्य विभाजक a और b इस प्रकार के सामान्य विभाजक हैं r_k−1 और 0. इस प्रकार r_k−1 का GCD है a और b. यह न केवल यह साबित करता है कि यूक्लिड का एल्गोरिदम जीसीडी की गणना करता है बल्कि यह भी साबित करता है कि जीसीडी मौजूद हैं।

बेज़ाउट की पहचान और विस्तारित जीसीडी एल्गोरिदम

बेज़ाउट की पहचान एक जीसीडी से संबंधित प्रमेय है, जो प्रारंभ में पूर्णांकों के लिए सिद्ध हुई, जो प्रत्येक प्रमुख आदर्श डोमेन के लिए मान्य है। एक क्षेत्र पर अविभाजित बहुपदों के मामले में, इसे निम्नानुसार कहा जा सकता है।

If g is the greatest common divisor of two polynomials a and b (not both zero), then there are two polynomials u and v such that

$au+bv=g\quad$ (Bézout's identity)

and either u = 1, v = 0, or u = 0, v = 1, or

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

बहुपदों के मामले में इस परिणाम का हित यह है कि बहुपदों की गणना करने के लिए एक कुशल एल्गोरिदम है u और v, यह एल्गोरिथम लूप के प्रत्येक पुनरावृत्ति पर की गई कुछ और संगणनाओं द्वारा यूक्लिड के एल्गोरिथम से भिन्न है। इसलिए इसे विस्तारित जीसीडी एल्गोरिथम कहा जाता है। यूक्लिड के एल्गोरिथ्म के साथ एक और अंतर यह है कि यह केवल शेष के बजाय यूक्लिडियन डिवीजन के भागफल, निरूपित क्वो का भी उपयोग करता है। यह एल्गोरिदम निम्नानुसार काम करता है।

Extended GCD algorithm

Input: a, b, univariate polynomials

Output:
    g, the GCD of a and b
    u, v, as in above statement
    a1, b1, such that
        ${\begin{aligned}a=ga_{1}\\b=gb_{1}\end{aligned}}$
Begin
    ${\begin{array}{ll}r_{0}=a&r_{1}=b\\s_{0}=1&s_{1}=0\\t_{0}=0&t_{1}=1\end{array}}$
  
    for (i = 1; ri ≠ 0; i = i+1) do
        $q=\operatorname {quo} (r_{i-1},r_{i})$
        ${\begin{aligned}r_{i+1}&=r_{i-1}-qr_{i}\\s_{i+1}&=s_{i-1}-qs_{i}\\t_{i+1}&=t_{i-1}-qt_{i}\end{aligned}}$
    end do
    ${\begin{aligned}g&=r_{i-1}\\u&=s_{i-1}\\v&=t_{i-1}\end{aligned}}$
    ${\begin{aligned}a_{1}&=(-1)^{i-1}t_{i}\\b_{1}&=(-1)^{i}s_{i}\end{aligned}}$
end

यह प्रमाण कि एल्गोरिथम अपने आउटपुट विनिर्देशन को संतुष्ट करता है, इस तथ्य पर निर्भर करता है कि, प्रत्येक के लिए i अपने पास

$r_{i}=as_{i}+bt_{i}$

$s_{i}t_{i+1}-t_{i}s_{i+1}=s_{i}t_{i-1}-t_{i}s_{i-1},$

बाद की समानता का अर्थ है

$s_{i}t_{i+1}-t_{i}s_{i+1}=(-1)^{i}.$

डिग्रियों पर अभिकथन इस तथ्य से अनुसरण करता है कि, प्रत्येक पुनरावृत्ति पर, की डिग्रियाँ s_i और t_i की डिग्री के रूप में अधिक से अधिक वृद्धि r_i घटता है।

इस एल्गोरिथम की एक दिलचस्प विशेषता यह है कि, जब बेज़ाउट की पहचान के गुणांक की आवश्यकता होती है, तो किसी को उनके GCD द्वारा इनपुट बहुपदों का भागफल मुफ्त में मिलता है।

बीजगणितीय विस्तार का अंकगणित

विस्तारित GCD एल्गोरिथम का एक महत्वपूर्ण अनुप्रयोग यह है कि यह किसी को बीजगणितीय विस्तार में विभाजन की गणना करने की अनुमति देता है।

होने देना L किसी क्षेत्र का बीजगणितीय विस्तार K, एक तत्व द्वारा उत्पन्न जिसका न्यूनतम बहुपद f की डिग्री है n. के तत्व L को आमतौर पर अविभाजित बहुपदों द्वारा दर्शाया जाता है K डिग्री से कम n.

में जोड़ L केवल बहुपदों का जोड़ है:

$a+_{L}b=a+_{K[X]}b.$

में गुणन L बहुपदों का गुणन है जिसके बाद विभाजन होता है f:

$a\cdot _{L}b=\operatorname {rem} (a._{K[X]}b,f).$

एक गैर शून्य तत्व का व्युत्क्रम a का L गुणांक है u बेज़ाउट की पहचान में au + fv = 1, जिसकी गणना विस्तारित GCD एल्गोरिथम द्वारा की जा सकती है। (जीसीडी 1 है क्योंकि न्यूनतम बहुपद f अलघुकरणीय है)। विस्तारित जीसीडी एल्गोरिथ्म के विनिर्देश में डिग्री असमानता से पता चलता है कि एक और विभाजन द्वारा {{mvar|f}डिग्री प्राप्त करने के लिए } की आवश्यकता नहीं है (u) <आप (f).

उपपरिणामी

अविभाज्य बहुपदों के मामले में, सबसे बड़े सामान्य विभाजक और परिणामी के बीच एक मजबूत संबंध होता है। अधिक सटीक रूप से, दो बहुपदों P, Q का परिणाम P और Q के गुणांकों का एक बहुपद फलन है जिसका मान शून्य है यदि और केवल यदि P और Q का GCD स्थिर नहीं है।

उप-परिणाम सिद्धांत इस संपत्ति का एक सामान्यीकरण है जो सामान्य रूप से दो बहुपदों के GCD को चिह्नित करने की अनुमति देता है, और परिणामी 0-th उप-परिणामी बहुपद है। i-वें उपपरिणामी बहुपद S_iदो बहुपदों का (पी, क्यू) पी और क्यू अधिक से अधिक डिग्री का एक बहुपद है जिसका गुणांक पी और क्यू के गुणांकों के बहुपद कार्य हैं, और i-वां प्रमुख उपपरिणाम गुणांक s_i(पी, क्यू) एस की डिग्री i का गुणांक है_i(पी क्यू)। उनके पास संपत्ति है कि पी और क्यू की जीसीडी की डिग्री डी है अगर और केवल अगर

$s_{0}(P,Q)=\cdots =s_{d-1}(P,Q)=0\ ,s_{d}(P,Q)\neq 0$.

इस मामले में एस_d(पी, क्यू) पी और क्यू की जीसीडी है और

$S_{0}(P,Q)=\cdots =S_{d-1}(P,Q)=0.$

उप-परिणामी बहुपदों के प्रत्येक गुणांक को पी और क्यू के सिल्वेस्टर मैट्रिक्स के एक उप-मैट्रिक्स के निर्धारक के रूप में परिभाषित किया गया है। इसका तात्पर्य है कि उप-परिणामस्वरूप अच्छी तरह से विशेषज्ञ हैं। अधिक सटीक रूप से, किसी भी क्रमविनिमेय वलय R पर बहुपदों के लिए उपपरिणामों को परिभाषित किया गया है, और निम्नलिखित संपत्ति है।

चलो φ एक अन्य कम्यूटेटिव रिंग S में R का रिंग होमोमोर्फिज्म है। यह एक और होमोमोर्फिज्म तक फैला हुआ है, जिसे R और S पर बहुपदों के छल्ले के बीच भी दर्शाया गया है। फिर, यदि P और Q R में गुणांक वाले अविभाज्य बहुपद हैं जैसे कि

$\deg(P)=\deg(\varphi (P))$

और

$\deg(Q)=\deg(\varphi (Q)),$

फिर φ(P) और φ(Q) के उपपरिणामी बहुपद और प्रमुख उपपरिणाम गुणांक, P और Q के φ द्वारा छवि हैं।

उपपरिणामकर्ताओं में दो महत्वपूर्ण गुण होते हैं जो उन्हें पूर्णांक गुणांक वाले दो बहुपदों के GCD के कंप्यूटरों पर गणना के लिए मौलिक बनाते हैं। सबसे पहले, निर्धारकों के माध्यम से उनकी परिभाषा, हैडमार्ड असमानता के माध्यम से, GCD के गुणांकों के आकार को सीमित करने की अनुमति देती है। दूसरे, यह बाध्य और अच्छी विशेषज्ञता की संपत्ति मॉड्यूलर अंकगणित और चीनी शेष प्रमेय के माध्यम से पूर्णांक गुणांक वाले दो बहुपदों के जीसीडी की गणना करने की अनुमति देती है (#मॉड्यूलर जीसीडी एल्गोरिदम देखें)।

तकनीकी परिभाषा

होने देना

$P=p_{0}+p_{1}X+\cdots +p_{m}X^{m},\quad Q=q_{0}+q_{1}X+\cdots +q_{n}X^{n}.$

एक क्षेत्र K में गुणांक वाले दो अविभाज्य बहुपद हैं। आइए हम द्वारा निरूपित करें ${\mathcal {P}}_{i}$ i से कम घात वाले बहुपदों के आयाम i का K सदिश स्थान। गैर-ऋणात्मक पूर्णांक i के लिए i ≤ m और i ≤ n, मान लीजिए

$\varphi _{i}:{\mathcal {P}}_{n-i}\times {\mathcal {P}}_{m-i}\rightarrow {\mathcal {P}}_{m+n-i}$

रैखिक नक्शा ऐसा हो

$\varphi _{i}(A,B)=AP+BQ.$

P और Q का परिणाम सिल्वेस्टर मैट्रिक्स का निर्धारक है, जो कि (वर्ग) का मैट्रिक्स है $\varphi _{0}$ एक्स की शक्तियों के आधार पर। इसी तरह, i-subresultant बहुपद को मैट्रिक्स के सबमेट्रिसेस के निर्धारकों के संदर्भ में परिभाषित किया गया है $\varphi _{i}.$ आइए हम इन मैट्रिक्स का अधिक सटीक वर्णन करें;

चलो पी_i = 0 i < 0 या i > m, और q के लिए_i = 0 i < 0 या i > n के लिए। सिल्वेस्टर मैट्रिक्स (एम + एन) × (एम + एन) - मैट्रिक्स है जैसे कि आई-वें पंक्ति और जे-वें कॉलम का गुणांक पी है_m+j−i जे ≤ एन और क्यू के लिए_j−i जम्मू > एन के लिए:

$S={\begin{pmatrix}p_{m}&0&\cdots &0&q_{n}&0&\cdots &0\\p_{m-1}&p_{m}&\cdots &0&q_{n-1}&q_{n}&\cdots &0\\p_{m-2}&p_{m-1}&\ddots &0&q_{n-2}&q_{n-1}&\ddots &0\\\vdots &\vdots &\ddots &p_{m}&\vdots &\vdots &\ddots &q_{n}\\\vdots &\vdots &\cdots &p_{m-1}&\vdots &\vdots &\cdots &q_{n-1}\\p_{0}&p_{1}&\cdots &\vdots &q_{0}&q_{1}&\cdots &\vdots \\0&p_{0}&\ddots &\vdots &0&q_{0}&\ddots &\vdots &\\\vdots &\vdots &\ddots &p_{1}&\vdots &\vdots &\ddots &q_{1}\\0&0&\cdots &p_{0}&0&0&\cdots &q_{0}\end{pmatrix}}.$

मैट्रिक्स टी_iका $\varphi _{i}$ S का (m + n − i) × (m + n − 2i)-सबमैट्रिक्स है जो कॉलम 1 से n − i और n + 1 से m + के सबमैट्रिक्स में शून्य की अंतिम i पंक्तियों को हटाकर प्राप्त किया जाता है। n − i of S (जो प्रत्येक ब्लॉक में i कॉलम और i शून्य की अंतिम पंक्तियों को हटा रहा है)। प्रमुख उपपरिणामी गुणांक एस_im + n − 2i T की पहली पंक्तियों का निर्धारक है_i.

फ्लाइट वी_i(m + n − 2i) × (m + n − i) आव्यूह इस प्रकार परिभाषित हो। सबसे पहले हम (m + n − 2i − 1) × (m + n − 2i − 1) पहचान मैट्रिक्स के दाईं ओर (i + 1) शून्य के कॉलम जोड़ते हैं। फिर हम परिणामी मैट्रिक्स के निचले हिस्से को एक पंक्ति से जोड़ते हैं जिसमें (m + n - i - 1) शून्य और उसके बाद X होता है^आई, एक्सⁱ⁻¹, ..., X, 1:

$V_{i}={\begin{pmatrix}1&0&\cdots &0&0&0&\cdots &0\\0&1&\cdots &0&0&0&\cdots &0\\\vdots &\vdots &\ddots &\vdots &\vdots &\ddots &\vdots &0\\0&0&\cdots &1&0&0&\cdots &0\\0&0&\cdots &0&X^{i}&X^{i-1}&\cdots &1\end{pmatrix}}.$

इस अंकन के साथ, i-th उपपरिणामी बहुपद मैट्रिक्स उत्पाद V का निर्धारक है_iT_i. डिग्री j का इसका गुणांक T के वर्ग सबमैट्रिक्स का निर्धारक है_iइसकी m + n − 2i − 1 पहली पंक्ति और (m + n − i − j)-वीं पंक्ति शामिल है।

सबूत का खाका

यह स्पष्ट नहीं है कि, जैसा कि परिभाषित किया गया है, उप-परिणामस्वरूपों में वांछित गुण होते हैं। फिर भी, यदि रैखिक बीजगणित और बहुपदों के गुणों को एक साथ रखा जाए तो उपपत्ति काफी सरल है।

परिभाषित के रूप में, मैट्रिक्स टी के कॉलम_iकी छवि से संबंधित कुछ बहुपदों के गुणांक के वैक्टर हैं $\varphi _{i}$. i-वें उपपरिणामी बहुपद S की परिभाषा_iदिखाता है कि इसके गुणांकों का वेक्टर इन कॉलम वैक्टरों का एक रैखिक संयोजन है, और इस प्रकार एस_iकी छवि के अंतर्गत आता है $\varphi _{i}.$ यदि GCD की डिग्री i से अधिक है, तो बेज़ाउट की पहचान दर्शाती है कि प्रत्येक गैर शून्य बहुपद की छवि में $\varphi _{i}$ i से बड़ी डिग्री है। इसका तात्पर्य यह है कि एस_i= 0।

यदि, दूसरी ओर, GCD की डिग्री i है, तो बेज़ाउट की पहचान फिर से यह साबित करने की अनुमति देती है कि GCD के गुणक जिनकी डिग्री m + n − i से कम है, की छवि में हैं $\varphi _{i}$. इन गुणकों के सदिश स्थान का आयाम m + n − 2i है और इसमें युग्मवार विभिन्न अंशों के बहुपदों का आधार है, जो i से छोटा नहीं है। इसका तात्पर्य यह है कि m + n − 2i का सबमैट्रिक्स, T के कॉलम सोपानक रूप की पहली पंक्तियाँ_iपहचान मैट्रिक्स है और इस प्रकार एस_i0 नहीं है। इस प्रकार एस_iकी छवि में एक बहुपद है $\varphi _{i}$, जो GCD का गुणक है और समान डिग्री है। इस प्रकार यह एक महानतम सामान्य विभाजक है।

जीसीडी और रूट फाइंडिंग

वर्ग मुक्त गुणनखंड

Main article: Square-free factorization

अधिकांश रूट-फाइंडिंग एल्गोरिदम बहुपदों के साथ खराब व्यवहार करते हैं जिनमें कई जड़ें होती हैं। इसलिए रूट-फाइंडिंग एल्गोरिथम को कॉल करने से पहले उनका पता लगाना और उन्हें हटाना उपयोगी है। एक GCD संगणना कई जड़ों के अस्तित्व का पता लगाने की अनुमति देती है, क्योंकि एक बहुपद की कई जड़ें बहुपद के GCD और उसके औपचारिक व्युत्पन्न की जड़ें होती हैं।

बहुपद और उसके व्युत्पन्न के GCD की गणना करने के बाद, आगे की GCD संगणनाएँ बहुपद का पूर्ण वर्ग-मुक्त गुणनखंडन प्रदान करती हैं, जो कि एक गुणनखंड है

$f=\prod _{i=1}^{\deg(f)}f_{i}^{i}$

जहाँ, प्रत्येक i के लिए, बहुपद f_i या तो 1 है यदि f में बहुलता i की कोई जड़ नहीं है या एक वर्ग-मुक्त बहुपद है (जो बहुपद के बिना एक बहुपद है) जिसकी जड़ें f की बहुलता i की जड़ें हैं (देखें वर्ग-मुक्त बहुपद#Yun's कलन विधि| यूं का एल्गोरिदम)।

इस प्रकार वर्ग-मुक्त गुणनखंड बहु-जड़ों वाले बहुपद की जड़-खोज को कम डिग्री के कई वर्ग-मुक्त बहुपदों के मूल-खोज में कम कर देता है। वर्ग-मुक्त गुणनखंडन भी अधिकांश बहुपद गुणनखंडन एल्गोरिदम में पहला कदम है।

स्टॉर्म सीक्वेंस

Main article: Sturm sequence

वास्तविक गुणांकों के साथ एक बहुपद का स्टर्म अनुक्रम, बहुपद और इसके व्युत्पन्न पर लागू यूक्लिड के एल्गोरिथ्म के एक संस्करण द्वारा प्रदान किए गए अवशेषों का क्रम है। स्टर्म सीक्वेंस प्राप्त करने के लिए, व्यक्ति बस निर्देश को बदल देता है

$r_{i+1}:=\operatorname {rem} (r_{i-1},r_{i})$

यूक्लिड के एल्गोरिथ्म द्वारा

$r_{i+1}:=-\operatorname {rem} (r_{i-1},r_{i}).$

वी (ए) अनुक्रम में संकेतों के परिवर्तनों की संख्या होने दें, जब बिंदु ए पर मूल्यांकन किया जाता है। स्टर्म के प्रमेय का दावा है कि वी (ए) - वी (बी) अंतराल [ए, बी] में बहुपद की वास्तविक जड़ों की संख्या है। इस प्रकार स्टर्म अनुक्रम किसी दिए गए अंतराल में वास्तविक जड़ों की संख्या की गणना करने की अनुमति देता है। अंतराल को उप-विभाजित करके जब तक कि प्रत्येक उप-अंतराल में अधिकतम एक जड़ न हो, यह एक एल्गोरिथ्म प्रदान करता है जो वास्तविक जड़ों को मनमाने ढंग से छोटी लंबाई के अंतराल में ढूँढता है।

जीसीडी एक अंगूठी और उसके अंशों के क्षेत्र पर

इस खंड में, हम एक अद्वितीय गुणनखंडन डोमेन R पर बहुपदों पर विचार करते हैं, आमतौर पर पूर्णांकों की अंगूठी, और इसके अंश F के क्षेत्र पर, आमतौर पर परिमेय संख्याओं के क्षेत्र पर, और हम R[X] और F[X] को निरूपित करते हैं इन वलयों पर चरों के समुच्चय में बहुपदों के वलय।

आदिम भाग-सामग्री गुणनखंड

See also: Content (algebra) and Gauss's lemma (polynomial)

एक बहुपद p ∈ R[X] की सामग्री, जिसे cont(p) द्वारा निरूपित किया जाता है, इसके गुणांकों का GCD है। एक बहुपद q ∈ F[X] लिखा जा सकता है

$q={\frac {p}{c}}$

जहाँ p ∈ R[X] और c ∈ R: c के लिए q के गुणांकों के सभी हरों का गुणज (उदाहरण के लिए उनका गुणनफल) और p = cq लेना पर्याप्त है। क्यू की सामग्री को इस प्रकार परिभाषित किया गया है:

$\operatorname {cont} (q)={\frac {\operatorname {cont} (p)}{c}}.$

दोनों ही मामलों में, सामग्री को आर की एक इकाई (रिंग थ्योरी) द्वारा गुणन तक परिभाषित किया गया है।

आर [एक्स] या एफ [एक्स] में एक बहुपद का आदिम भाग द्वारा परिभाषित किया गया है

$\operatorname {primpart} (p)={\frac {p}{\operatorname {cont} (p)}}.$

दोनों ही मामलों में, यह R[X] में एक बहुपद है जो आदिम है, जिसका अर्थ है कि 1 इसके गुणांकों का GCD है।

इस प्रकार R[X] या F[X] में प्रत्येक बहुपद को गुणनखंडित किया जा सकता है

$p=\operatorname {cont} (p)\,\operatorname {primpart} (p),$

और यह गुणनखंड R की एक इकाई द्वारा सामग्री के गुणा और इस इकाई के व्युत्क्रम द्वारा आदिम भाग के गुणन तक अद्वितीय है।

गॉस की लेम्मा का तात्पर्य है कि दो आदिम बहुपदों का गुणनफल आदिम है। यह इस प्रकार है कि

$\operatorname {primpart} (pq)=\operatorname {primpart} (p)\operatorname {primpart} (q)$

और

$\operatorname {cont} (pq)=\operatorname {cont} (p)\operatorname {cont} (q).$

=== R और F === के ऊपर GCD के बीच संबंध

पूर्ववर्ती खंड के संबंध आर [एक्स] और एफ [एक्स] में जीसीडी के बीच एक मजबूत संबंध का संकेत देते हैं। अस्पष्टता से बचने के लिए, अंकन gcd को अनुक्रमित किया जाएगा, निम्नलिखित में, जिस रिंग में GCD की गणना की जाती है।

अगर क्यू₁ और क्यू₂ F [X] से संबंधित हैं, तो

$\operatorname {primpart} (\gcd _{F[X]}(q_{1},q_{2}))=\gcd _{R[X]}(\operatorname {primpart} (q_{1}),\operatorname {primpart} (q_{2})).$

अगर प₁ और पी₂ आर [एक्स] से संबंधित हैं, फिर

$\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})),$

और

$\gcd _{R[X]}(\operatorname {primpart} (p_{1}),\operatorname {primpart} (p_{2}))=\operatorname {primpart} (\gcd _{F[X]}(p_{1},p_{2})).$

इस प्रकार बहुपद जीसीडी की गणना अनिवार्य रूप से एफ [एक्स] और आर [एक्स] पर एक ही समस्या है।

परिमेय संख्याओं पर अविभाज्य बहुपदों के लिए, कोई सोच सकता है कि यूक्लिड का एल्गोरिथ्म GCD की गणना के लिए एक सुविधाजनक तरीका है। हालाँकि, इसमें बड़ी संख्या में पूर्णांकों के अंशों को सरल बनाना शामिल है, और परिणामी एल्गोरिथ्म कुशल नहीं है। इस कारण से, पूर्णांकों पर केवल बहुपदों के साथ काम करने के लिए यूक्लिड के एल्गोरिथ्म को संशोधित करने के तरीकों को डिजाइन किया गया है। इनमें यूक्लिडियन डिवीजन को बदलना शामिल है, जो एक तथाकथित छद्म-विभाजन द्वारा अंशों का परिचय देता है, और यूक्लिड के एल्गोरिथ्म के शेष अनुक्रम को तथाकथित छद्म-शेष अनुक्रमों द्वारा प्रतिस्थापित करता है (देखें #छद्म-शेष अनुक्रम)।

=== सबूत है कि जीसीडी बहुभिन्नरूपी बहुपद === के लिए मौजूद है

पिछले अनुभाग में हमने देखा है कि R[X] में बहुपदों का GCD, R और F[X] के GCDs से निकाला जा सकता है। सबूत पर करीब से देखने से पता चलता है कि यह हमें आर [एक्स] में जीसीडी के अस्तित्व को साबित करने की इजाजत देता है, अगर वे आर और एफ [एक्स] में मौजूद हैं। विशेष रूप से, यदि जीसीडी आर में मौजूद है, और यदि एक्स को एक चर में घटाया जाता है, तो यह साबित करता है कि जीसीडी आर [एक्स] में मौजूद है (यूक्लिड का एल्गोरिदम एफ [एक्स] में जीसीडी के अस्तित्व को साबित करता है)।

n चरों में एक बहुपद को (n - 1) चरों में बहुपदों के वलय पर एक अविभाजित बहुपद के रूप में माना जा सकता है। इस प्रकार चरों की संख्या पर एक पुनरावृत्ति से पता चलता है कि यदि GCD मौजूद हैं और R में गणना की जा सकती है, तो वे मौजूद हैं और R पर प्रत्येक बहुभिन्नरूपी बहुपद रिंग में गणना की जा सकती है। विशेष रूप से, यदि R या तो पूर्णांकों का वलय है या एक क्षेत्र है। , तो R[x में GCD मौजूद हैं₁,..., एक्स_n], और जो पूर्ववर्ती उन्हें गणना करने के लिए एल्गोरिदम प्रदान करता है।

प्रमाण है कि एक अद्वितीय कारककरण डोमेन पर एक बहुपद अंगूठी भी एक अद्वितीय कारककरण डोमेन समान है, लेकिन यह एल्गोरिदम प्रदान नहीं करता है, क्योंकि किसी क्षेत्र पर अविभाजित बहुपदों को कारक करने के लिए कोई सामान्य एल्गोरिदम नहीं है (ऐसे क्षेत्रों के उदाहरण हैं जिनके लिए वहां अविभाज्य बहुपदों के लिए कोई गुणनखंड एल्गोरिथम मौजूद नहीं है)।

छद्म शेष अनुक्रम

इस खंड में, हम एक अभिन्न डोमेन Z (आमतौर पर पूर्णांकों का वलय 'Z') और इसके अंशों के क्षेत्र Q (आमतौर पर परिमेय संख्याओं का क्षेत्र 'Q') पर विचार करते हैं। अविभाजित बहुपद रिंग Z[X] में दो बहुपद A और B दिए गए हैं, A द्वारा B का यूक्लिडियन विभाजन (Q से अधिक) एक भागफल और शेषफल प्रदान करता है जो Z[X] से संबंधित नहीं हो सकता है।

के लिए, यदि कोई यूक्लिड के एल्गोरिथ्म को निम्नलिखित बहुपदों पर लागू करता है

$X^{8}+X^{6}-3X^{4}-3X^{3}+8X^{2}+2X-5$

और

$3X^{6}+5X^{4}-4X^{2}-9X+21,$

यूक्लिड के एल्गोरिथ्म के क्रमिक अवशेष हैं

${\begin{aligned}&-{\tfrac {5}{9}}X^{4}+{\tfrac {1}{9}}X^{2}-{\tfrac {1}{3}},\\&-{\tfrac {117}{25}}X^{2}-9X+{\tfrac {441}{25}},\\&{\tfrac {233150}{19773}}X-{\tfrac {102500}{6591}},\\&-{\tfrac {1288744821}{543589225}}.\end{aligned}}$

एक देखता है कि इनपुट बहुपदों के गुणांकों की छोटी डिग्री और छोटे आकार के बावजूद, किसी को बड़े आकार के पूर्णांक अंशों में हेरफेर और सरलीकरण करना पड़ता है।

छद्म-विभाजन को यूक्लिड के एल्गोरिथम के एक प्रकार की अनुमति देने के लिए पेश किया गया है जिसके लिए सभी अवशेष Z[X] से संबंधित हैं।

अगर $\deg(A)=a$ और $\deg(B)=b$ और ए ≥ बी, बी द्वारा ए के छद्म-विभाजन का 'छद्म शेष', प्रेम (ए, बी) द्वारा चिह्नित है

$\operatorname {prem} (A,B)=\operatorname {rem} (\operatorname {lc} (B)^{a-b+1}A,B),$

कहाँ lc(B) B का अग्रणी गुणांक है (X का गुणांक^बी).

Z[X] में दो बहुपदों के छद्म-विभाजन का छद्म-शेष हमेशा Z[X] का होता है।

एक 'छद्म-शेष अनुक्रम' (छद्म) शेष r का अनुक्रम है_i निर्देश को बदलकर प्राप्त किया

$r_{i+1}:=\operatorname {rem} (r_{i-1},r_{i})$

यूक्लिड के एल्गोरिथ्म द्वारा

$r_{i+1}:={\frac {\operatorname {prem} (r_{i-1},r_{i})}{\alpha }},$

जहां α Z का एक तत्व है जो अंश के प्रत्येक गुणांक को बिल्कुल विभाजित करता है। α के अलग-अलग विकल्प अलग-अलग छद्म-शेष अनुक्रम देते हैं, जो अगले उपखंडों में वर्णित हैं।

जैसा कि दो बहुपदों के सामान्य विभाजक नहीं बदले जाते हैं यदि बहुपदों को व्युत्क्रमणीय स्थिरांक (क्यू में) से गुणा किया जाता है, छद्म-शेष अनुक्रम में अंतिम गैर शून्य शब्द इनपुट बहुपदों का जीसीडी (क्यू [एक्स] में) है। इसलिए, छद्म-शेष अनुक्रम Q [X] में GCD की गणना करने की अनुमति देता है बिना Q में अंशों को पेश किए।

कुछ संदर्भों में, छद्म शेष के प्रमुख गुणांक के चिह्न को नियंत्रित करना आवश्यक है। यह आम तौर पर मामला है जब परिणामी और उपपरिणाम की गणना करते हैं, या स्टर्म के प्रमेय का उपयोग करने के लिए। यह नियंत्रण या तो बदलकर किया जा सकता है lc(B) छद्म शेष की परिभाषा में इसके निरपेक्ष मान से, या के चिन्ह को नियंत्रित करके α (अगर α शेष के सभी गुणांकों को विभाजित करता है, वही सत्य है –α).

तुच्छ छद्म शेष अनुक्रम

सबसे सरल (परिभाषित करने के लिए) शेष अनुक्रम में हमेशा लेना होता है α = 1. व्यवहार में, यह दिलचस्प नहीं है, क्योंकि गुणांक का आकार इनपुट बहुपद की डिग्री के साथ तेजी से बढ़ता है। यह पूर्ववर्ती खंड के उदाहरण पर स्पष्ट रूप से प्रकट होता है, जिसके लिए क्रमिक छद्म अवशेष हैं

$-15\,X^{4}+3\,X^{2}-9,$

$15795\,X^{2}+30375\,X-59535,$

$1254542875143750\,X-1654608338437500,$

$12593338795500743100931141992187500.$

एल्गोरिथम के प्रत्येक पुनरावृत्ति पर क्रमिक अवशेषों के गुणांक के अंकों की संख्या दोगुनी से अधिक है। यह तुच्छ छद्म-शेष अनुक्रमों का विशिष्ट व्यवहार है।

आदिम छद्म शेष अनुक्रम

आदिम छद्म-शेष अनुक्रम में अंश की सामग्री को α के लिए लेना शामिल है। इस प्रकार सभी आर_i आदिम बहुपद हैं।

आदिम छद्म-शेष अनुक्रम छद्म-शेष अनुक्रम है, जो सबसे छोटे गुणांक उत्पन्न करता है। हालाँकि इसके लिए Z में कई GCD की गणना करने की आवश्यकता होती है, और इसलिए व्यवहार में उपयोग करने के लिए पर्याप्त रूप से कुशल नहीं है, खासकर जब Z स्वयं एक बहुपद वलय है।

पिछले अनुभागों के समान इनपुट के साथ, क्रमिक अवशेष, उनकी सामग्री द्वारा विभाजन के बाद हैं

$-5\,X^{4}+X^{2}-3,$

$13\,X^{2}+25\,X-49,$

$4663\,X-6150,$

$1.$

गुणांक का छोटा आकार इस तथ्य को छुपाता है कि जीसीडी द्वारा कई पूर्णांक जीसीडी और डिवीजनों की गणना की गई है।

उप-परिणामी छद्म-शेष अनुक्रम

छद्म अवशेषों के साथ एक उप-परिणामी अनुक्रम की गणना भी की जा सकती है। इस प्रक्रिया में α को इस तरह से चुनना शामिल है कि प्रत्येक r_i एक परिणामी बहुपद है। हैरानी की बात है, α की गणना बहुत आसान है (नीचे देखें)। दूसरी ओर, एल्गोरिथम की शुद्धता का प्रमाण कठिन है, क्योंकि इसे लगातार दो शेषों की डिग्री के अंतर के लिए सभी संभावनाओं को ध्यान में रखना चाहिए।

उप-परिणामी अनुक्रम में गुणांक आदिम छद्म-शेष अनुक्रम की तुलना में शायद ही कभी बहुत बड़े होते हैं। जैसा कि Z में GCD संगणनाओं की आवश्यकता नहीं है, छद्म-शेषों के साथ उप-परिणामी अनुक्रम सबसे कुशल संगणना देता है।

पिछले अनुभागों के समान इनपुट के साथ, क्रमिक अवशेष हैं

$15\,X^{4}-3\,X^{2}+9,$

$65\,X^{2}+125\,X-245,$

$9326\,X-12300,$

$260708.$

गुणांक का एक उचित आकार है। वे बिना किसी जीसीडी संगणना के प्राप्त किए जाते हैं, केवल सटीक विभाजन। यह इस एल्गोरिथम को आदिम छद्म-शेष अनुक्रमों की तुलना में अधिक कुशल बनाता है।

छद्म-शेषों के साथ उप-परिणामी अनुक्रम की गणना करने वाला एल्गोरिथम नीचे दिया गया है। इस एल्गोरिथ्म में, input (a, b) Z[X] में बहुपदों का एक युग्म है। वह r_i Z[X], चर i और में क्रमिक छद्म अवशेष हैं d_i गैर-ऋणात्मक पूर्णांक हैं, और ग्रीक अक्षर Z में तत्वों को दर्शाते हैं। कार्य deg() और rem() एक बहुपद की डिग्री और यूक्लिडियन डिवीजन के शेष को निरूपित करें। एल्गोरिथम में, यह शेष हमेशा Z[X] में होता है। अंत में विभाजन निरूपित / हमेशा सटीक होते हैं और उनका परिणाम या तो Z [X] या Z में होता है।

${\begin{aligned}r_{0}:=a\\r_{1}:=b\end{aligned}}$
for ($i:=1$; $r_{i}\neq 0$; $i:=i+1;$) do
    ${\begin{aligned}d_{i}&:=\deg(r_{i-1})-\deg(r_{i})\\\gamma _{i}&:=\operatorname {lc} (r_{i})\end{aligned}}$
    if $i=1$ then
        ${\begin{aligned}\beta _{1}&:=(-1)^{d_{1}+1}\\\psi _{1}&:=-1\end{aligned}}$
    else
        ${\begin{aligned}\psi _{i}&:={\frac {(-\gamma _{i-1})^{d_{i-1}}}{\psi _{i-1}^{d_{i-1}-1}}}\\\beta _{i}&:=-\gamma _{i-1}\psi _{i}^{d_{i}}\end{aligned}}$
    end if
    $r_{i+1}:={\frac {\operatorname {rem} (\gamma _{i}^{d_{i}+1}r_{i-1},r_{i})}{\beta _{i}}}$
end do.

नोट: lc प्रमुख गुणांक के लिए खड़ा है, चर की उच्चतम डिग्री का गुणांक।

यह एल्गोरिथ्म न केवल सबसे बड़े सामान्य विभाजक (अंतिम गैर शून्य) की गणना करता है r_i), लेकिन साथ ही सभी उपपरिणामी बहुपद: शेष r_i है (deg(r_i−1) − 1)-वाँ उपपरिणामी बहुपद। अगर deg(r_i) < deg(r_i−1) − 1, द deg(r_i)-वाँ उपपरिणामी बहुपद है lc(r_i)^{deg(r_i−1)−deg(r_i)−1}r_i. अन्य सभी परिणामी बहुपद शून्य हैं।

छद्म अवशेषों के साथ स्टर्म अनुक्रम

स्टर्म अनुक्रमों के समान गुणों वाले अनुक्रमों के निर्माण के लिए छद्म अवशेषों का उपयोग किया जा सकता है। इसके लिए लगातार छद्म अवशेषों के संकेतों को नियंत्रित करने की आवश्यकता होती है, ताकि स्टर्म अनुक्रम के समान ही संकेत मिल सकें। यह निम्नानुसार एक संशोधित छद्म शेष को परिभाषित करके किया जा सकता है।

अगर $\deg(A)=a$ और $\deg(B)=b$ और a ≥ b, B द्वारा A के छद्म विभाजन का संशोधित छद्म शेष prem2(A, B) है

$\operatorname {prem2} (A,B)=-\operatorname {rem} (|\operatorname {lc} (B)|^{a-b+1}A,B),$

जहां |एलसी(बी)| बी के अग्रणी गुणांक का पूर्ण मूल्य है (एक्स का गुणांक^बी).

पूर्णांक गुणांक वाले इनपुट बहुपदों के लिए, यह पूर्णांक गुणांक वाले बहुपदों वाले स्टर्म अनुक्रमों की पुनर्प्राप्ति की अनुमति देता है। उप-परिणामस्वरूप छद्म-शेष अनुक्रम को इसी तरह संशोधित किया जा सकता है, इस मामले में शेष राशियों के संकेत परिमेय पर गणना किए गए संकेतों के साथ मेल खाते हैं।

ध्यान दें कि ऊपर दिए गए उप-परिणामस्वरूप छद्म-शेष अनुक्रम की गणना के लिए एल्गोरिथ्म गलत उप-परिणामस्वरूप बहुपदों की गणना करेगा यदि कोई उपयोग करता है $-\mathrm {prem2} (A,B)$ के बजाय $\operatorname {prem} (A,B)$.

मॉड्यूलर जीसीडी एल्गोरिदम

अगर एफ और जी कुछ निश्चित रूप से उत्पन्न फ़ील्ड एफ के लिए एफ [एक्स] में बहुपद हैं, तो यूक्लिडियन एल्गोरिदम उनके जीसीडी की गणना करने का सबसे स्वाभाविक तरीका है। हालाँकि, आधुनिक कंप्यूटर बीजगणित प्रणालियाँ केवल इसका उपयोग करती हैं यदि प्रतीकात्मक संगणना नामक घटना के कारण F परिमित है। हालांकि यूक्लिडियन एल्गोरिथम के दौरान डिग्री घटती रहती है, अगर एफ परिमित क्षेत्र नहीं है तो गणना के दौरान बहुपदों का बिट आकार (कभी-कभी नाटकीय रूप से) बढ़ सकता है क्योंकि एफ में बार-बार अंकगणितीय संचालन बड़े भावों को जन्म देता है। उदाहरण के लिए, दो परिमेय संख्याओं का योग, जिनके हर, b से परिबद्ध हैं, एक ऐसी परिमेय संख्या की ओर ले जाते हैं, जिसका हर b से परिबद्ध है।², इसलिए सबसे खराब स्थिति में, केवल एक ऑपरेशन के साथ बिट आकार लगभग दोगुना हो सकता है।

गणना में तेजी लाने के लिए, एक अंगूठी डी लें जिसके लिए एफ और जी डी [एक्स] में हैं, और एक आदर्श I लें जैसे कि डी/आई एक परिमित अंगूठी है। फिर यूक्लिडियन एल्गोरिथम के साथ इस परिमित वलय पर GCD की गणना करें। पुनर्निर्माण तकनीकों (चीनी शेष प्रमेय, तर्कसंगत पुनर्निर्माण (गणित), आदि) का उपयोग करके कोई व्यक्ति f और g की GCD को उसकी छवि मॉड्यूलो से कई आदर्शों I को पुनर्प्राप्त कर सकता है। कोई साबित कर सकता है यह काम करता है बशर्ते कि कोई गैर-न्यूनतम डिग्री के साथ मॉड्यूलर छवियों को त्याग दे, और आदर्शों I मॉड्यूलो से बचा जाए जो एक प्रमुख गुणांक गायब हो जाता है।

कल्पना करना $F=\mathbb {Q} ({\sqrt {3}})$, $D=\mathbb {Z} [{\sqrt {3}}]$, $f={\sqrt {3}}x^{3}-5x^{2}+4x+9$ और $g=x^{4}+4x^{2}+3{\sqrt {3}}x-6$. अगर हम लेते हैं $I=(2)$ तब $D/I$ एक परिमित वलय है (चूंकि कोई क्षेत्र नहीं है $I$ में अधिकतम नहीं है $D$). यूक्लिडियन एल्गोरिथ्म की छवियों पर लागू होता है $f,g$ में $(D/I)[x]$ सफल होता है और 1 लौटाता है। इसका तात्पर्य है कि GCD का $f,g$ में $F[x]$ 1 भी होना चाहिए। ध्यान दें कि इस उदाहरण को किसी भी विधि द्वारा आसानी से नियंत्रित किया जा सकता है क्योंकि अभिव्यक्ति प्रफुल्लित होने के लिए डिग्री बहुत छोटी थी, लेकिन यह दर्शाता है कि यदि दो बहुपदों में GCD 1 है, तो मॉड्यूलर एल्गोरिथ्म एकल आदर्श के बाद समाप्त होने की संभावना है $I$.

यह भी देखें

• बहुपद विषयों की सूची
• बहुभिन्नरूपी विभाजन एल्गोरिथ्म

संदर्भ

• Basu, Saugata; Pollack, Richard; Roy, Marie-Françoise (2006). Algorithms in real algebraic geometry, chapter 4.2. Springer-Verlag.
• Davenport, James H.; Siret, Yvon; Tournier, Évelyne (1988). Computer algebra: systems and algorithms for algebraic computation. Translated from the French by A. Davenport and J.H. Davenport. Academic Press. ISBN 978-0-12-204230-0.
• van Hoeij, M.; Monagan, M.B. (2004). Algorithms for polynomial GCD computation over algebraic function fields. ISSAC 2004. pp. 297–304.
• Javadi, S.M.M.; Monagan, M.B. (2007). A sparse modular GCD algorithm for polynomials over algebraic function fields. ISSAC 2007. pp. 187–194.
• Knuth, Donald E. (1969). The Art of Computer Programming II. Addison-Wesley. pp. 370–371.
• Knuth, Donald E. (1997). Seminumerical Algorithms. The Art of Computer Programming. Vol. 2 (Third ed.). Reading, Massachusetts: Addison-Wesley. pp. 439–461, 678–691. ISBN 0-201-89684-2.
• Loos, Rudiger (1982), "Generalized polynomial remainder sequences", in B. Buchberger; R. Loos; G. Collins (eds.), Computer Algebra, Springer Verlag