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

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

किसी क्षेत्र (गणित) पर अविभाजित बहुपदों के महत्वपूर्ण स्थिति में बहुपद 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) द्वारा निरूपित किया जाता है।

महत्तम समापवर्तक अद्वितीय नहीं है: यदि p और q के लिए d का GCD मान है, इसके पश्चात बहुपद 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 पर निर्भर करता हैं।

गुण

• जैसा कि ऊपर कहा गया है, दो बहुपदों का जीसीडी सम्मिलित है यदि गुणांक या तो क्षेत्र से संबंधित हैं, पूर्णांक की रिंग, या अधिक सामान्यतः अद्वितीय कारककरण डोमेन के लिए उपयोग किए जाते हैं।
• यदि 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 होगा क्योंकि इसमें सभी सामान्य विभाजक सम्मिलित हैं और यह एकात्मक मूल हैं।

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

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(...) डिग्री को दर्शाता है और शून्य बहुपद की डिग्री को ऋणात्मक के रूप में परिभाषित किया जाता है। इसके अतिरिक्त, q औरr विशिष्ट रूप से इन संबंधों द्वारा परिभाषित हैं।

पूर्णांकों के यूक्लिडियन विभाजन से अंतर यह है कि, पूर्णांकों के लिए, डिग्री को निरपेक्ष मान से परिवर्तित कर दिये जाते हैं, और अद्वितीयता रखने के लिए किसी को यह मान लेना चाहिए कि 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. यह न केवल यह प्रमाणित करता है कि यूक्लिड का एल्गोरिदम जीसीडी की गणना करता है बल्कि यह भी प्रमाणित करता है कि जीसीडी सम्मिलित हैं।

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

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

अगर g दो बहुपदों a और b (दोनों शून्य नहीं) का सबसे बड़ा सामान्य विभाजक है, तो दो बहुपद u हैं और v ऐसा कि

$au+bv=g\quad$ (बेज़ाउट की पहचान)

और या तो u = 1, v = 0, या u = 0, v = 1 , या

$\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) <up (f) डिग्री प्राप्त करने की आवश्यकता नहीं है।

उपपरिणामी

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

उप-परिणाम सिद्धांत इस संपत्ति का सामान्यीकरण है जो सामान्य रूप से दो बहुपदों के GCD को चिह्नित करने की अनुमति देता है, और परिणामी 0-th उप-परिणामी बहुपद है।

i-वें उपपरिणामी बहुपद S_iदो बहुपदों का (p, q) p और q अधिक से अधिक डिग्री का बहुपद है जिसका गुणांक p और q के गुणांकों के बहुपद कार्य हैं, और i-वां प्रमुख उपपरिणाम गुणांक s_i(p, q) s_i की डिग्री i का गुणांक (p q) है। उनके पास कुछ मान इस प्रकार हैं कि p और q की जीसीडी की डिग्री डी है यदि और केवल यदि

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

इस स्थिति में s_d(p, q) p और q की जीसीडी है और

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

उप-परिणामी बहुपदों के प्रत्येक गुणांक को p और q के सिल्वेस्टर आव्यूह के उप-आव्यूह के निर्धारक के रूप में परिभाषित किया गया है। इसका तात्पर्य है कि उप-परिणामस्वरूप विशेषकर हैं। जिसका अधिक सटीक रूप से, किसी भी क्रमविनिमेय वलय 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}$ x की शक्तियों के आधार पर। इसी प्रकार, i-परिणामी बहुपद को आव्यूह के सबमेट्रिसेस के निर्धारकों के संदर्भ में $\varphi _{i}.$ परिभाषित किया गया है।

आइए हम इन आव्यूह का अधिक सटीक वर्णन करें;

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

$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}}.$

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

फ्लाइट v_i(m + n − 2i) × (m + n − i) आव्यूह इस प्रकार परिभाषित होता हैं। सबसे पहले हम (m + n − 2i − 1) × (m + n − 2i − 1) पहचान आव्यूह के दाईं ओर (i + 1) शून्य के कॉलम जोड़ते हैं। फिर हम परिणामी आव्यूह के निचले हिस्से को पंक्ति से जोड़ते हैं जिसमें (m + n - i - 1) शून्य और उसके बाद Xⁱ 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_i T_iका निर्धारक है, इस प्रकार डिग्री j का इसका गुणांक T_i के वर्ग उपआव्यूह का निर्धारक है, इसकी m + n − 2i − 1 पहली पंक्ति और (m + n − i − j)-वीं पंक्ति सम्मिलित है।

प्रमाण का प्रारूप

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

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

यदि GCD की डिग्री i से अधिक है, तो बेज़ाउट की पहचान दर्शाती है कि प्रत्येक गैर शून्य बहुपद की प्रतिबिम्ब में $\varphi _{i}$ i से बड़ी डिग्री है। इसका तात्पर्य यह है कि s_i= 0।

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

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

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

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

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

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

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

जहाँ, प्रत्येक i के लिए, बहुपद f_i या तो 1 है यदि f में बहुलता i की कोई आधार नहीं है या वर्ग-मुक्त बहुपद है (जो बहुपद के बिना बहुपद है) जिसका आधार f की बहुलता i का आधार हैं (देखें वर्ग-मुक्त बहुपद U कलन विधि U का एल्गोरिदम)।

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

स्टॉर्म क्रम

Main article: स्टर्म सीक्वेंस

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

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

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

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

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

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

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

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

See also: सामग्री (बीजगणित) and गॉस की लेम्मा (बहुपद)

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

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

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

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

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

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

$\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 के बीच संबंध

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

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

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

यदि p₁ और p₂r [x] से संबंधित हैं, इस प्रकार

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

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

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

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

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

n चरों में बहुपद को (n - 1) चरों में बहुपदों के वलय पर अविभाजित बहुपद के रूप में माना जा सकता है। इस प्रकार चरों की संख्या पर पुनरावृत्ति से पता चलता है कि यदि GCD सम्मिलित हैं और R में गणना की जा सकती है, तो वे सम्मिलित हैं और R पर प्रत्येक बहुभिन्नरूपी बहुपद रिंग में गणना की जा सकती है। विशेष रूप से, यदि R या तो पूर्णांकों का वलय है या क्षेत्र है। , तो R[x में GCD सम्मिलित हैं₁,..., x_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$ और ए ≥ बी, बी द्वारा ए के छद्म-विभाजन का 'छद्म शेष', (a, b) द्वारा चिह्नित है

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

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

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 में) से गुणा किया जाता है, छद्म-शेष अनुक्रम में अंतिम गैर शून्य शब्द इनपुट बहुपदों का जीसीडी (q [x] में) है। इसलिए, छद्म-शेष अनुक्रम Q [X] में GCD की गणना करने की अनुमति देता है बिना Q में अंशों को प्रस्तुत किए जाते हैं।

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

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

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

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

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

$1254542875143750\,X-1654608338437500,$

$12593338795500743100931141992187500.$

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

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

आदिम छद्म-शेष अनुक्रम में अंश के मान को α के लिए लेना सम्मिलित है। इस प्रकार सभी r_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),$

जहां |LC(B)| B के अग्रणी गुणांक का पूर्ण मूल्य है। (x^b का गुणांक)

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

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

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

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

गणना में तेजी लाने के लिए, रिंग डी लें जिसके लिए f और जी डी [x] में और मानक होते हैं 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