ในพีชคณิตตัวหารร่วมมาก (มักย่อว่าGCDหรือgcd ) ของพหุนาม สองตัว คือพหุนามที่มีดีกรีสูงสุดที่เป็นไปได้ ซึ่งเป็นตัวประกอบของพหุนามทั้งสองตัวนั้น แนวคิดนี้คล้ายคลึงกับตัวหารร่วมมากของจำนวนเต็มสองจำนวน

ในกรณีสำคัญของ พหุนาม ตัวแปรเดียวบนฟิลด์ ตัวหารร่วมมาก ของพหุนามสามารถคำนวณได้เช่นเดียวกับตัวหารร่วมมากของจำนวนเต็ม โดย ใช้ อัลกอริทึมยุคลิด โดย ใช้ การ หารยาวตัวหารร่วมมากของพหุนามนั้นถูกกำหนดไว้เฉพาะการคูณด้วยค่าคงที่ที่ผกผันได้ เท่านั้น

ความคล้ายคลึงกันระหว่างตัวหารร่วมมากของจำนวนเต็มและตัวหารร่วมมากของพหุนามทำให้สามารถขยายคุณสมบัติทั้งหมดที่สามารถอนุมานได้จากขั้นตอนวิธีแบบยุคลิดและการหารแบบยุคลิด ไปยังพหุนามตัวแปรเดียวได้ ยิ่งไปกว่านั้น ตัวหารร่วมมากของพหุนามยังมีคุณสมบัติเฉพาะที่ทำให้มันเป็นแนวคิดพื้นฐานในสาขาต่างๆ ของพีชคณิต โดยทั่วไปรากของตัวหารร่วมมากของพหุนามสองตัวจะเป็นรากร่วมของพหุนามทั้งสอง และสิ่งนี้ให้ข้อมูลเกี่ยวกับรากโดยไม่ต้องคำนวณ ตัวอย่างเช่นรากซ้ำของพหุนามคือรากของตัวหารร่วมมากของพหุนามและอนุพันธ์ของมัน และการคำนวณตัวหารร่วมมากเพิ่มเติมช่วยให้สามารถคำนวณการแยกตัวประกอบแบบไม่มีกำลังสองของพหุนาม ซึ่งให้พหุนามที่มีรากเป็นรากของจำนวนซ้ำ ที่กำหนด ของพหุนามดั้งเดิม

ตัวหารร่วมมากสามารถนิยามและมีอยู่ได้โดยทั่วไป สำหรับพหุนามหลายตัวแปรบนฟิลด์ บนวงแหวนของจำนวนเต็ม และบนโดเมนการแยกตัวประกอบที่ไม่ซ้ำกัน ใดๆ มีอัลกอริทึมในการคำนวณตัวหารร่วมมากอยู่แล้ว ตราบใดที่มีอัลกอริทึมหาตัวหารร่วมมากในวงแหวนของสัมประสิทธิ์ อัลกอริทึมเหล่านี้ดำเนินการโดยใช้การเรียกซ้ำตามจำนวนตัวแปรเพื่อลดปัญหาให้เป็นรูปแบบหนึ่งของอัลกอริทึมแบบยุคลิด อัลกอริทึมเหล่านี้เป็นเครื่องมือพื้นฐานในพีชคณิตคอมพิวเตอร์เนื่องจากระบบพีชคณิตคอมพิวเตอร์ใช้มันอย่างเป็นระบบเพื่อลดรูปเศษส่วน ซึ่งเป็นแรงบันดาลใจสำคัญสำหรับทฤษฎีสมัยใหม่ของตัวหารร่วมมากของพหุนาม

ให้pและqเป็นพหุนามที่มีสัมประสิทธิ์อยู่ในโดเมนเชิงอินทิกรัลFซึ่งโดยทั่วไป คือ ฟิลด์หรือจำนวนเต็ม ตัวหารร่วมมากของpและqคือพหุนามdที่หารpและq ลงตัว และตัวหารร่วมทุกตัวของpและqก็หารd ลงตัวด้วย พหุนามทุกคู่ (ที่ไม่ใช่ศูนย์ทั้งคู่) จะมีตัวหารร่วมมากก็ต่อเมื่อFเป็นโดเมนการแยกตัวประกอบที่ไม่ซ้ำกัน

ถ้าFเป็นฟิลด์ และpกับqไม่เป็นศูนย์ทั้งคู่ พหุนามdจะเป็นตัวหารร่วมมากก็ต่อเมื่อมันหารทั้งpและq ลงตัว และมีดีกรีสูงสุดในบรรดาพหุนามที่มีคุณสมบัตินี้ ถ้าp = q = 0ตัวหารร่วมมากจะเป็น 0 อย่างไรก็ตาม ผู้เขียนบางคนมองว่าในกรณีนี้ตัวหารร่วมมากนั้นหาค่าไม่ได้

ตัวหารร่วมมากที่สุดของpและqมักจะใช้สัญลักษณ์gcd( p , q )แทน

ตัวหารร่วมมากจะมีเอกลักษณ์เฉพาะตัวก็ต่อเมื่อมีการคูณด้วยค่าคงที่ที่ผกผันได้เท่านั้น กล่าวคือ ถ้าdเป็นตัวหารร่วมมากของpและqแล้ว พหุนามcจะเป็นตัวหารร่วมมากอีกตัวหนึ่งก็ต่อเมื่อมีสมาชิกu ที่ผกผันได้ ในFเช่นนั้น ในกรณีของจำนวนเต็ม ความกำกวมนี้อาจถูกขจัดได้โดยการเลือกตัวหารร่วมมากที่เป็นบวกที่มีเอกลักษณ์ แทนที่จะเป็นลบ สำหรับพหุนามตัวแปรเดียวเหนือฟิลด์ เราสามารถเลือกตัวหารร่วมมากมาตรฐานให้เป็น ตัวเลือก เอกนาม ที่มีเอกลักษณ์ (มีสัมประสิทธิ์นำหน้าเป็น 1) แต่เหนือวงแหวนสัมประสิทธิ์ทั่วไปนั้นไม่มีตัวเลือกมาตรฐาน ดังนั้น ความเท่าเทียมกันเช่นd = gcd( p , q )หรือgcd( p , q ) = gcd( r , s )ควรเข้าใจว่าหมายถึง " dเป็นตัวหารร่วมมากของpและq " และ " pและqมีชุดตัวหารร่วมมากชุดเดียวกันกับrและs " โดยเฉพาะอย่างยิ่งgcd( p , q ) = 1หมายความว่าค่าคงที่ที่ผกผันได้เป็นตัวหารร่วมเพียงอย่างเดียว ในกรณีนี้ โดยเปรียบเทียบกับวงแหวนของจำนวนเต็ม เราสามารถกล่าวได้ว่าpและqคือ$${\displaystyle c=ud\quad {\text{ และ }}\quad d=u^{-1}c.}$$พหุนามที่ไม่มีตัวหารร่วม

• ดังที่กล่าวไว้ข้างต้น ตัวหารร่วมมาก (GCD) ของพหุนามสองตัวจะมีอยู่ได้ก็ต่อเมื่อสัมประสิทธิ์ของพหุนามเหล่า นั้นอยู่ในฟิลด์ วงแหวนของจำนวนเต็ม หรือโดยทั่วไปแล้วอยู่ในโดเมนการแยกตัวประกอบที่ไม่ซ้ำกัน
• ถ้าcเป็นตัวหารร่วมใดๆ ของpและqแล้วcจะหารตัวหารร่วมมาก (GCD) ของทั้งสองลงตัว
• ${\displaystyle \gcd(p,q)=\gcd(q,p).}$
• ${\displaystyle \gcd(p,q)=\gcd(q,p+rq)}$สำหรับพหุนามr ใดๆ คุณสมบัตินี้เป็นพื้นฐานของการพิสูจน์อัลกอริทึมแบบยุคลิด
• สำหรับองค์ประกอบผกผันได้ใดๆkของวงแหวนสัมประสิทธิ์.${\displaystyle \gcd(p,q)=\gcd(p,kq)}$
• ดังนั้นสำหรับสเกลาร์ใดๆที่ทำให้สามารถผกผันได้${\displaystyle \gcd(p,q)=\gcd(a_{1}p+b_{1}q,a_{2}p+b_{2}q)}$${\displaystyle a_{1},b_{1},a_{2},b_{2}}$${\displaystyle a_{1}b_{2}-a_{2}b_{1}}$
• ถ้าเช่นนั้น${\displaystyle \gcd(p,r)=1}$${\displaystyle \gcd(p,q)=\gcd(p,qr)}$
• ถ้าเช่นนั้น${\displaystyle \gcd(q,r)=1}$${\displaystyle \gcd(p,qr)=\gcd(p,q)\,\gcd(p,r)}$
• สำหรับพหุนามเอกตัวแปรสองตัวpและqบนฟิลด์ จะมีพหุนามaและb อยู่ ซึ่งและหารลงตัวในทุกการรวมเชิงเส้นของpและq ( เอกลักษณ์ของเบซูต์ )${\displaystyle \gcd(p,q)=ap+bq}$${\displaystyle \gcd(p,q)}$
• ตัวหารร่วมมากของพหุนามสามตัวขึ้นไปสามารถนิยามได้ในทำนองเดียวกันกับพหุนามสองตัว โดยสามารถคำนวณได้แบบเวียนซ้ำจากตัวหารร่วมมากของพหุนามสองตัวโดยใช้เอกลักษณ์ดังนี้: และ$${\displaystyle \gcd(p,q,r)=\gcd(p,\gcd(q,r)),}$$$${\displaystyle \gcd(p_{1},p_{2},\dots ,p_{n})=\gcd(p_{1},\gcd(p_{2},\dots ,p_{n})).}$$

มีหลายวิธีในการหาตัวหารร่วมมากที่สุดของพหุนามสองตัว วิธีสองวิธีนั้นได้แก่:

1. การแยกตัวประกอบของพหุนามคือการหาตัวประกอบของแต่ละพหุนาม จากนั้นเลือกชุดตัวประกอบร่วมที่พหุนามทุกตัวมีร่วมกันจากแต่ละชุดตัวประกอบ วิธีนี้อาจมีประโยชน์เฉพาะในกรณีที่ง่ายเท่านั้น เพราะโดยทั่วไปแล้วการแยกตัวประกอบนั้นยากกว่าการหาตัวหารร่วมมาก
2. อัลกอริทึมของยุคลิดสามารถใช้หา ห.ร.ม. ของพหุนามสองตัวในลักษณะเดียวกับการหา ห.ร.ม. ของจำนวนสองจำนวนได้

ในการหา ห.ร.ม. ของพหุนามสองนามโดยใช้การแยกตัวประกอบ ให้แยกตัวประกอบของพหุนามทั้งสองให้สมบูรณ์ จากนั้น นำผลคูณของตัวประกอบร่วมทั้งหมด ในขั้นตอนนี้ เราอาจยังไม่ได้พหุนามเอกลักษณ์ ดังนั้น สุดท้ายให้คูณผลลัพธ์ด้วยค่าคงที่เพื่อให้ได้พหุนามเอกลักษณ์ ผลลัพธ์นี้จะเป็นตัว ห.ร.ม. ของพหุนามทั้งสอง เนื่องจากมีตัวหารร่วมทั้งหมดและเป็นพหุนามเอกลักษณ์

^{ตัวอย่าง ที่} หนึ่ง: จง หา ห.ร.ม. ของx² + 7x + 6และx² − ^5x − 6

ดังนั้น ตัวหารร่วมมาก (GCD) ของพวกเขาก็คือx + 1

การแยกตัวประกอบพหุนามอาจเป็นเรื่องยาก โดยเฉพาะอย่างยิ่งถ้าพหุนามมีดีกรีสูงวิธีการของยุคลิดเป็นวิธีที่ใช้ได้กับพหุนามทุกคู่ โดยใช้การหารแบบยุคลิด ซ้ำๆ เมื่อใช้วิธีการนี้กับจำนวนสองจำนวน ขนาดของจำนวนจะลดลงในแต่ละขั้นตอน สำหรับพหุนาม ดีกรีของพหุนามจะลดลงในแต่ละขั้นตอน เศษเหลือที่ไม่เป็นศูนย์สุดท้าย ซึ่งหากจำเป็นก็ทำให้เป็นพหุนาม เอกลักษณ์ จะ เป็นตัวหารร่วมมาก (GCD) ของพหุนามทั้งสอง

โดยเฉพาะอย่างยิ่ง ในการหา ห.ร.ม. ของพหุนามสองตัว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 )และr0 ( x ) _{ลงตัว}ดังนั้น เมื่อกำหนดให้ เราสามารถทำซ้ำการหารแบบยุคลิดเพื่อให้ได้พหุนามใหม่_q1 ( x ) , r1 ( x ), a2 ( x ), b2 ( x )และอื่นๆ ต่อไป ในแต่ละขั้นตอน เราจะได้ _{ดังนั้นลำดับ} จะไปถึงจุดหนึ่งซึ่ง และในที่สุด _เรา ก็ได้ GCD: $${\displaystyle \gcd(a(x),b(x))=\gcd(b(x),r_{0}(x)).}$$$${\displaystyle a_{1}(x)=b(x),b_{1}(x)=r_{0}(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 :

เนื่องจาก12x + 12เป็นเศษเหลือที่ไม่เป็นศูนย์ตัวสุดท้าย จึงเป็นตัวหารร่วมมาก (GCD) ของพหุนามดั้งเดิม และตัวหารร่วมมากแบบเอกลักษณ์(monic GCD )คือ x + 1

ในตัวอย่างนี้ การหลีกเลี่ยงการใส่ตัวหารโดยการดึง 12 ออกมาก่อนขั้นตอนที่สองนั้นไม่ใช่เรื่องยาก สามารถทำได้เสมอโดยใช้ลำดับเศษเหลือเทียมแต่หากไม่ระมัดระวัง อาจทำให้ได้จำนวนเต็มขนาดใหญ่มากในระหว่างการคำนวณ ดังนั้นสำหรับการคำนวณด้วยคอมพิวเตอร์ จึงมีการใช้อัลกอริทึมอื่น ซึ่งจะอธิบายไว้ด้านล่าง

วิธีนี้ใช้ได้ผลก็ต่อเมื่อสามารถทดสอบความเท่ากับศูนย์ของสัมประสิทธิ์ที่เกิดขึ้นระหว่างการคำนวณได้ ดังนั้นในทางปฏิบัติ สัมประสิทธิ์ต้องเป็นจำนวนเต็มจำนวนตรรกยะสมาชิกของฟิลด์จำกัดหรือต้องเป็นของฟิลด์ส่วนขยายที่สร้างขึ้นอย่างจำกัดของฟิลด์ใดฟิลด์หนึ่งข้างต้น หากสัมประสิทธิ์เป็นจำนวนทศนิยมที่แสดงถึงจำนวนจริงที่ทราบค่าโดยประมาณเท่านั้น จะต้องทราบดีกรีของตัวหารร่วมมาก (GCD) เพื่อให้ได้ ผลลัพธ์ ที่เสถียรทางตัวเลขในกรณีนี้ อาจใช้วิธีการอื่น ซึ่งโดยทั่วไปแล้วจะใช้การแยกส่วนค่าเอกพจน์ (singular value decomposition )

กรณีพื้นฐานของพหุนามตัวแปรเดียวบนฟิลด์นั้นมีความสำคัญเป็นพิเศษ มันเป็นตัวอย่างที่ง่ายที่สุดนอกเหนือจากวงแหวนของจำนวนเต็ม และความคล้ายคลึงนี้เป็นที่มาของแนวคิดเรื่องโดเมนยุคลิดทฤษฎีและอัลกอริธึมสำหรับ กรณี พหุนามหลายตัวแปรและสำหรับสัมประสิทธิ์ในโดเมนการแยกตัวประกอบที่ไม่ซ้ำกันนั้นขึ้นอยู่กับกรณีพื้นฐานเป็นอย่างมาก อัลกอริธึมหาตัวหารร่วมมากของพหุนามและอัลกอริธึมที่ได้มาจากกรณีพื้นฐานนี้ช่วยให้เราได้รับข้อมูลที่เป็นประโยชน์เกี่ยวกับรากของพหุนามโดยไม่ต้องคำนวณรากเหล่านั้น

การหารพหุนามแบบยุคลิด ซึ่งใช้ในอัลกอริทึมของยุคลิดสำหรับการคำนวณตัวหารร่วมมาก (GCD) นั้นคล้ายคลึงกับการหารจำนวนเต็มแบบยุคลิด มาก การมีอยู่ของการหารแบบนี้ขึ้นอยู่กับทฤษฎีบทต่อไปนี้: กำหนดให้พหุนามเอกตัวแปรสองตัวและที่กำหนดบนฟิลด์จะมีพหุนามสองตัว( ผลหาร ) และ( เศษเหลือ ) ที่สอดคล้องกับ และ โดยที่ " deg(...) " หมายถึงดีกรี และดีกรีของพหุนามศูนย์ถูกกำหนดให้เป็นลบ ยิ่งไปกว่านั้นqและrถูกกำหนดอย่างไม่ซ้ำกันโดยความสัมพันธ์เหล่านี้ ${\textstyle a}$${\displaystyle b\neq 0}$${\displaystyle q}$${\displaystyle r}$$${\displaystyle a=bq+r}$$$${\displaystyle \deg(r)<\deg(b),}$$

ความแตกต่างจากการหารจำนวนเต็มแบบยุคลิดก็คือ สำหรับจำนวนเต็มนั้น ดีกรีจะถูกแทนที่ด้วยค่าสัมบูรณ์ และเพื่อให้มีความเป็นเอกลักษณ์ จะต้องสมมติว่าrเป็นจำนวนที่ไม่เป็นลบ วงแหวนที่ทฤษฎีบทดังกล่าวมีอยู่เรียกว่าโดเมนยุคลิด

เช่นเดียวกับจำนวนเต็ม การหารพหุนามแบบยุคลิดสามารถคำนวณได้โดยใช้ อัลกอริทึมการ หารยาวอัลกอริทึมนี้มักนำเสนอสำหรับการคำนวณด้วยกระดาษและดินสอ แต่ก็ใช้งานได้ดีบนคอมพิวเตอร์เมื่อกำหนดเป็นทางการดังต่อไปนี้ (โปรดทราบว่าชื่อของตัวแปรตรงกับบริเวณบนแผ่นกระดาษในการคำนวณการหารยาวด้วยดินสอและกระดาษ) ในการคำนวณต่อไปนี้ "deg" หมายถึงดีกรีของตัวแปร (ตามธรรมเนียมdeg(0) < 0 ) และ "lc" หมายถึงสัมประสิทธิ์นำหน้า ซึ่งเป็นสัมประสิทธิ์ของดีกรีสูงสุดของตัวแปร

การหารแบบยุคลิด

อินพุต: aและ b ≠ 0 พหุนามสองตัวในตัวแปร x ; เอาต์พุต: qผลหาร และ rเศษเหลือ;

เริ่ม

q  := 0 r  := a d  := deg( b ) c  := lc( b ) ในขณะที่ deg( r ) ≥ d ทำซ้ำ s  := (lc( r )/ c ) ⋅ x deg( r )− d q  := q + s r  := r − sb สิ้นสุดการทำซ้ำ ส่งคืน ( q , r ) 

จบ

การพิสูจน์ความถูกต้องของอัลกอริทึมนี้อาศัยข้อเท็จจริงที่ว่า ตลอดลูป "while" เราจะได้a = bq + rและdeg( r )เป็นจำนวนเต็มที่ไม่เป็นลบซึ่งลดลงในแต่ละรอบ ดังนั้น การพิสูจน์ความถูกต้องของอัลกอริทึมนี้จึงเป็นการพิสูจน์ความถูกต้องของการหารแบบยุคลิดด้วยเช่นกัน

สำหรับจำนวนเต็ม การหารแบบยุคลิดทำให้เราสามารถกำหนดอัลกอริทึมของยุคลิดสำหรับการคำนวณหาตัวหารร่วมมากได้

เริ่มต้นจากพหุนามสองตัวคือaและbอัลกอริทึมของยูคลิดประกอบด้วยการแทนที่คู่( a , b )ด้วย( b , rem( a , b )) ซ้ำๆ (โดยที่ " rem( a , b ) " หมายถึงเศษเหลือจากการหารแบบยูคลิด ซึ่งคำนวณโดยอัลกอริทึมในส่วนก่อนหน้า) จนกระทั่งb = 0 ตัวหารร่วมมาก (GCD) คือเศษเหลือที่ไม่เป็นศูนย์ตัวสุดท้าย

อัลกอริทึมของยูคลิดสามารถเขียนในรูปแบบการเขียนโปรแกรมแบบเรียกซ้ำได้ดังนี้: $${\displaystyle \gcd(a,b):={\begin{cases}a&{\text{ถ้า }}b=0\\\gcd(b,\operatorname {rem} (a,b))&{\text{มิฉะนั้น}}.\end{cases}}}$$

ใน รูปแบบ การเขียนโปรแกรมเชิงคำสั่ง อัลกอริทึมเดียวกันนี้จะกลายเป็นแบบเดียวกัน โดยตั้งชื่อให้กับเศษเหลือระหว่างขั้นตอนแต่ละส่วน:

r ₀  := a r ₁  := b

สำหรับ ( i  := 1; r _i ≤ 0; i  := i + 1)ทำ

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

จบทำ

ส่งคืน 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สิ่งนี้ไม่เพียงแต่พิสูจน์ว่าอัลกอริทึมของยูคลิดคำนวณตัวหารร่วมมากได้ แต่ยังพิสูจน์ได้ว่าตัวหารร่วมมากมี อยู่จริง

เอกลักษณ์ของเบซูต์เป็นทฤษฎีบทที่เกี่ยวข้องกับตัวหารร่วมมาก (GCD) ซึ่งพิสูจน์ครั้งแรกสำหรับจำนวนเต็ม และใช้ได้กับโดเมนไอเดียลหลัก ทุกโดเมน ในกรณีของพหุนามตัวแปรเดียวเหนือฟิลด์ สามารถกล่าวได้ดังนี้

ถ้า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อัลกอริทึมนี้แตกต่างจากอัลกอริทึมของยุคลิดตรงที่มีการคำนวณเพิ่มเติมอีกเล็กน้อยในแต่ละรอบของการวนซ้ำ ดังนั้นจึงเรียกว่าอัลกอริทึม GCD แบบขยายความแตกต่างอีกประการหนึ่งกับอัลกอริทึมของยุคลิดคือ มันยังใช้ผลหาร (quo) ของการหารแบบยุคลิดแทนที่จะใช้เพียงเศษเหลือ อัลกอริทึมนี้ทำงานดังต่อไปนี้

อัลกอริทึม GCD แบบขยาย

อินพุต: a , b , พหุนามตัวแปรเดียว

ผลลัพธ์:

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; r i ≠ 0; i  := i +1)ทำq  := quo( r i −1 , r i ) r i +1  := r i −1 − qr i s i +1  := s i −1 − qs i t i +1  := t i −1 − qt i จบการทำ g  := r i −1 u  := s i −1 v  := t i −1 a 1  := (−1) i −1 t i b 1  := (−1) i s i

จบ

การพิสูจน์ว่าอัลกอริทึมตรงตามข้อกำหนดเอาต์พุตนั้นอาศัยข้อเท็จจริงที่ว่า สำหรับทุกiเราจะมี ความเท่าเทียมกันดังกล่าว ซึ่งหมายความว่า ข้อความยืนยันเกี่ยวกับระดับดีกรีนั้นมาจากข้อเท็จจริงที่ว่า ในทุกรอบการทำซ้ำ ระดับดีกรีของs _iและt _iจะเพิ่มขึ้นอย่างมากที่สุดเท่ากับระดับดีกรีของr _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}.}$$

คุณลักษณะที่น่าสนใจอย่างหนึ่งของอัลกอริธึมนี้คือ เมื่อต้องการสัมประสิทธิ์ของเอกลักษณ์ของเบซูต์ เราจะได้ผลหารของพหุนามที่ป้อนเข้าโดยใช้ตัวหารร่วมมาก (GCD) โดยอัตโนมัติ

การประยุกต์ใช้ที่สำคัญอย่างหนึ่งของอัลกอริทึม GCD แบบขยายคือ ช่วยให้สามารถคำนวณการหารในส่วนขยายของฟิลด์พีชคณิตได้

ให้Lเป็นส่วนขยายเชิงพีชคณิตของฟิลด์Kซึ่งสร้างขึ้นโดยองค์ประกอบที่มีพหุนามขั้นต่ำf ที่ มีดีกรีnโดย ทั่วไปแล้ว องค์ประกอบของLจะถูกแทนด้วยพหุนามตัวแปรเดียวเหนือKที่มีดีกรีน้อยกว่าn

การบวกในLนั้นก็คือการบวกพหุนามนั่นเอง: $${\displaystyle a+_{L}b=a+_{K[X]}b.}$$

การคูณในLคือการคูณพหุนามแล้วหารด้วยf : $${\displaystyle a\cdot _{L}b=\operatorname {rem} (a._{K[X]}b,f).}$$

ตัวผกผันขององค์ประกอบที่ไม่เป็นศูนย์aของLคือสัมประสิทธิ์uในเอกลักษณ์ของ Bézout au + fv = 1ซึ่งสามารถคำนวณได้โดยใช้อัลกอริทึม GCD แบบขยาย (GCD คือ 1 เพราะพหุนามขั้นต่ำfไม่สามารถแยกตัวประกอบได้) ความไม่เท่าเทียมกันของดีกรีในข้อกำหนดของอัลกอริทึม GCD แบบขยายแสดงให้เห็นว่าไม่จำเป็นต้องหารด้วยf เพิ่มเติม เพื่อให้ได้ deg( u ) < deg( f )

ในกรณีของพหุนามตัวแปรเดียว มีความสัมพันธ์ที่แน่นแฟ้นระหว่างตัวหารร่วมมากกับผลลัพธ์กล่าวคือ ผลลัพธ์ของพหุนามสองตัวPและQเป็นฟังก์ชันพหุนามของสัมประสิทธิ์ของPและQซึ่งจะมีค่าเป็นศูนย์ก็ต่อเมื่อตัวหารร่วมมากของPและQไม่คงที่

ทฤษฎีซับเรซูลแทนท์เป็นการวางนัยทั่วไปของคุณสมบัตินี้ที่ช่วยให้สามารถกำหนดลักษณะทั่วไปของ GCD ของพหุนามสองตัว และผลลัพธ์คือพหุนามซับเรซูลแทนท์ลำดับที่ 0 ^{[ 1 ]}

พหุนามผลลัพธ์ย่อยลำดับที่i _Si ( P , Q )ของพหุนามPและQ สองตัว คือพหุนามที่มีดีกรีไม่เกินiซึ่งสัมประสิทธิ์เป็นฟังก์ชันพหุนามของสัมประสิทธิ์ของPและQและสัมประสิทธิ์ผลลัพธ์ย่อยหลักลำดับที่i _Si ( P , Q )คือสัมประสิทธิ์ดีกรีiของSi ( _P , Q ) พหุนามทั้ง สองนี้มีคุณสมบัติว่า ตัวหารร่วมมาก (GCD) ของ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โดยที่ และ แล้วพหุนามผลลัพธ์ย่อยและสัมประสิทธิ์ผลลัพธ์ย่อยหลักของφ ( P )และφ ( Q )คือภาพที่ได้จากφของพหุ นาม ผลลัพธ์ ย่อยและสัมประสิทธิ์ผลลัพธ์ย่อยหลักของ PและQ$${\displaystyle \deg(P)=\deg(\varphi (P))}$$$${\displaystyle \deg(Q)=\deg(\varphi (Q)),}$$

ผลลัพธ์ย่อยมีคุณสมบัติสำคัญสองประการที่ทำให้เป็นพื้นฐานสำหรับการคำนวณตัวหารร่วมมาก (GCD) ของพหุนามสองตัวที่มีสัมประสิทธิ์เป็นจำนวนเต็มบนคอมพิวเตอร์ ประการแรก นิยามของผลลัพธ์ย่อยผ่านดีเทอร์มิแนนต์ช่วยให้สามารถกำหนดขอบเขตของขนาดสัมประสิทธิ์ของ GCD ได้โดยใช้ความไม่เท่าเทียมกันของฮาดามาร์ดประการที่สอง ขอบเขตนี้และคุณสมบัติของการเลือกที่ดีช่วยให้สามารถคำนวณ GCD ของพหุนามสองตัวที่มีสัมประสิทธิ์เป็นจำนวนเต็มได้โดยใช้การคำนวณแบบโมดูลาร์และทฤษฎีบทเศษเหลือของจีน (ดูด้านล่าง )

ให้ และ เป็นพหุนามตัวแปรเดียวสองตัวที่มีสัมประสิทธิ์อยู่ในฟิลด์Kให้เราแทนด้วยปริภูมิเวกเตอร์Kมิติiของพหุนามที่มีดีกรีน้อยกว่าiสำหรับจำนวนเต็มที่ไม่เป็นลบiโดยที่i ≤ mและi ≤ nให้ เป็นฟังก์ชันเชิงเส้นเช่นนั้น $${\displaystyle P=p_{0}+p_{1}X+\cdots +p_{m}X^{m},\quad Q=q_{0}+q_{1}X+\cdots +q_{n}X^{n}.}$$${\displaystyle {\คณิตศาสตร์ {P}__{i}}$$${\displaystyle \varphi _{i}:{\mathcal {P}__{ni}\times {\mathcal {P}__{mi}\rightarrow {\mathcal {P}__{m+ni}}$$$${\displaystyle \varphi _{i}(A,B)=AP+BQ.}$$

ผลลัพธ์ของPและQคือดีเทอร์มิแนนต์ของเมทริกซ์ซิลเวสเตอร์ซึ่งเป็นเมทริกซ์ (จัตุรัส) ของบนฐานของกำลังของXในทำนองเดียวกัน พหุนามผลลัพธ์ย่อยที่ iถูกกำหนดในรูปของดีเทอร์มิแนนต์ของเมทริกซ์ย่อยของเมทริกซ์ของ${\displaystyle \varphi _{0}}$${\displaystyle \varphi _{i}.}$

เรามาอธิบายเมทริกซ์เหล่านี้ให้ละเอียดขึ้นกันดีกว่า;

ให้p _i = 0สำหรับi < 0หรือi > mและq _i = 0สำหรับi < 0หรือi > nเมทริกซ์ซิลเวสเตอร์คือ เมทริกซ์ขนาด ( m + n ) × ( m + n )โดยที่สัมประสิทธิ์ของ แถวที่ iและ คอลัมน์ที่ jคือp _{m + j − i}สำหรับj ≤ nและq _{j − i}สำหรับj > n : ^{[หมายเหตุ 1 ]}$${\displaystyle 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คือเมท ริกซ์ย่อยขนาด ( m + n − i ) × ( m + n − 2 i )ของS ซึ่งได้มาจากการลบแถวศูนย์ i แถว สุดท้ายในเมทริกซ์ย่อยของคอลัมน์ที่ 1 ถึงn − iและn + 1ถึงm + n − iของS (นั่นคือการลบiคอลัมน์ในแต่ละบล็อกและiแถวศูนย์สุดท้าย) สัมประสิทธิ์ผลลัพธ์ย่อยหลักs _iคือดีเทอร์มิแนนต์ของm + n − 2 iแถว แรกของT _i${\displaystyle \varphi _{i}}$

ให้Vi _เป็นเมท ริกซ์ขนาด ( m + n − 2i ) × ( m + n − i )ที่กำหนดดังต่อไปนี้ ขั้นแรก เราเพิ่ม คอลัมน์ศูนย์ ( i + 1)คอลัมน์ทางด้านขวาของเมทริกซ์เอกลักษณ์ขนาด( m + n − 2i − 1) × ( m + n − 2i − 1) จากนั้น เรากำหนดขอบด้านล่างของเมทริกซ์ที่ได้ด้วยแถวที่ประกอบด้วยศูนย์( m + n − i − 1)ตัว ตามด้วยXi , Xi ^{− 1 ,} ..., X , 1 : $${\displaystyle 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คือดีเทอร์มิแนนต์ของผลคูณเมทริกซ์V _i T _iสัมประสิทธิ์ของดีกรีj ของพหุนามนี้ คือดีเทอร์มิแนนต์ของเมทริกซ์ย่อยจัตุรัสของT _iซึ่งประกอบด้วยแถวที่m + n − 2 i − 1แถวแรก และแถวที่ ( m + n − i − j )

ไม่ใช่เรื่องชัดเจนว่าผลลัพธ์ย่อยตามที่กำหนดไว้นั้นมีคุณสมบัติที่ต้องการหรือไม่ อย่างไรก็ตาม การพิสูจน์นั้นค่อนข้างง่ายหากนำ คุณสมบัติของ พีชคณิตเชิงเส้น และคุณสมบัติของพหุนามมารวมกัน

ตามคำจำกัดความ คอลัมน์ของเมทริกซ์T _iคือเวกเตอร์ของสัมประสิทธิ์ของพหุนามบางตัวที่อยู่ในภาพของนิยามของพหุนามผลลัพธ์ย่อยที่i S _iแสดงให้เห็นว่าเวกเตอร์ของสัมประสิทธิ์ของมันคือการรวมเชิงเส้นของเวกเตอร์คอลัมน์เหล่านี้ และดังนั้นS _iจึงอยู่ในภาพของ${\displaystyle \varphi _{i}}$${\displaystyle \varphi _{i}.}$

ถ้าดีกรีของตัวหารร่วมมาก (GCD) มากกว่าiแล้วเอกลักษณ์ของเบซูต์จะแสดงให้เห็นว่าพหุนามที่ไม่เป็นศูนย์ทุกตัวในภาพของจะมีดีกรีมากกว่าiซึ่งหมายความว่าS _i = 0 ${\displaystyle \varphi _{i}}$

ในทางกลับกัน ถ้าดีกรีของตัวหารร่วมมาก (GCD) คือiแล้วเอกลักษณ์ของเบซูต์จะช่วยให้พิสูจน์ได้อีกครั้งว่าพหุคูณของ GCD ที่มีดีกรีต่ำกว่าm + n − iอยู่ในภาพของปริภูมิเวกเตอร์ของพหุคูณเหล่านี้มีมิติm + n − 2 iและมีฐานเป็นพหุนามที่มีดีกรีต่างกันเป็นคู่ๆ ซึ่งไม่น้อยกว่าiนี่หมายความว่าเมทริกซ์ย่อยของ แถว m + n − 2 iแรกของรูปแบบขั้นบันไดคอลัมน์ของT _iคือเมทริกซ์เอกลักษณ์ และดังนั้นs _i จึง ไม่ใช่ 0 ดังนั้นS _iจึงเป็นพหุนามในภาพของซึ่งเป็นพหุคูณของ GCD และมีดีกรีเดียวกัน ดังนั้นจึงเป็นตัวหารร่วมมาก ${\displaystyle \varphi _{i}}$${\displaystyle \varphi _{i}}$

อัลกอริทึมหาค่ารากส่วนใหญ่ทำงานได้ไม่ดีกับพหุนามที่มีรากหลายรากดังนั้นจึงเป็นประโยชน์ที่จะตรวจจับและกำจัดรากเหล่านั้นก่อนที่จะเรียกใช้อัลกอริทึมหาค่าราก การคำนวณหาตัวหารร่วมมาก (GCD) ช่วยให้สามารถตรวจจับการมีอยู่ของรากหลายรากได้ เนื่องจากรากหลายรากของพหุนามคือรากของตัวหารร่วมมากของพหุนามและอนุพันธ์ ของ มัน

หลังจากคำนวณตัวหารร่วมมาก (GCD) ของพหุนามและอนุพันธ์แล้ว การคำนวณ GCD เพิ่มเติมจะให้การแยกตัวประกอบแบบไม่มีตัวประกอบกำลังสอง สมบูรณ์ ของพหุนาม ซึ่งเป็นการแยกตัวประกอบ ที่สำหรับแต่ละiพหุนามf _iจะเป็น 1 ถ้าfไม่มีรากซ้ำiหรือเป็นพหุนามแบบไม่มีตัวประกอบกำลังสอง (นั่นคือพหุนามที่ไม่มีรากซ้ำ) ซึ่งรากของมันคือรากซ้ำiของf อย่างแน่นอน (ดูอัลกอริทึมของ Yun ) $${\displaystyle f=\prod _{i=1}^{\deg(f)}f_{i}^{i}}$$

ดังนั้น การแยกตัวประกอบแบบไม่มีตัวประกอบกำลังสองจึงช่วยลดการหาค่ารากของพหุนามที่มีรากหลายรากให้เหลือเพียงการหาค่ารากของพหุนามแบบไม่มีตัวประกอบกำลังสองที่มีดีกรีต่ำกว่าหลายๆ พหุนาม การแยกตัวประกอบแบบไม่มีตัวประกอบกำลังสองยังเป็นขั้นตอนแรกในอัลกอริทึม การแยกตัวประกอบพหุนามส่วน ใหญ่ด้วย

ลำดับสเติร์มของพหุนามที่มีสัมประสิทธิ์เป็นจำนวนจริง คือลำดับของเศษเหลือที่ได้จากวิธีการของยุคลิดแบบดัดแปลงที่ใช้กับพหุนามและอนุพันธ์ของมัน ในการหาลำดับสเติร์มนั้น เพียงแค่แทนที่คำสั่ง ของวิธีการของยุคลิดด้วย $${\displaystyle r_{i+1}:=\operatorname {rem} (r_{i-1},r_{i})}$$$${\displaystyle 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 ] แทนวงแหวนของพหุนามในชุดตัวแปรเหนือวงแหวนเหล่านี้

เนื้อหาของพหุนามp ∈ R [ X ]ซึ่งเขียนแทนด้วย " cont( p ) " คือ ตัวหารร่วมมาก (GCD) ของสัมประสิทธิ์ของพหุนามนั้น พหุนามq ∈ F [ X ]อาจเขียนได้ ดังนี้ โดยที่p ∈ R [ X ]และc ∈ R : เพียงแค่เลือกcเป็นผลคูณของตัวส่วนทั้งหมดของสัมประสิทธิ์ของq (เช่น ผลคูณของสัมประสิทธิ์เหล่านั้น) และp = cq เนื้อหาของ q ถูกกำหนดดังนี้:ใน ทั้งสองกรณี เนื้อหาจะถูกกำหนดโดยการคูณด้วยหน่วยของR$${\displaystyle q={\frac {p}{c}}}$$$${\displaystyle \operatorname {cont} (q)={\frac {\operatorname {cont} (p)}{c}}.}$$

ส่วนดั้งเดิมของพหุนามในR [ X ]หรือF [ X ]ถูกกำหนดโดย $${\displaystyle \operatorname {primpart} (p)={\frac {p}{\operatorname {cont} (p)}}.}$$

ในทั้งสองกรณี พหุนามนั้นเป็นพหุนามในR [ X ]ที่เป็น พหุ นามดั้งเดิมซึ่งหมายความว่า 1 เป็นตัวหารร่วมมากของสัมประสิทธิ์

ดังนั้นพหุนามทุกตัวในR [ X ]หรือF [ X ]สามารถแยกตัวประกอบได้ดังนี้ และการแยกตัวประกอบนี้มีเอกลักษณ์เฉพาะตัว ยกเว้นการคูณเนื้อหาด้วยหน่วยของRและการคูณส่วนดั้งเดิมด้วยส่วนกลับของหน่วยนี้ $${\displaystyle p=\operatorname {cont} (p)\,\operatorname {primpart} (p),}$$

ทฤษฎีบทของเกาส์บ่งชี้ว่า ผลคูณของพหุนามดั้งเดิมสองตัวก็เป็นพหุนามดั้งเดิมเช่นกัน ดังนั้นจึงสรุปได้ว่า และ $${\displaystyle \operatorname {primpart} (pq)=\operatorname {primpart} (p)\operatorname {primpart} (q)}$$$${\displaystyle \operatorname {cont} (pq)=\operatorname {cont} (p)\operatorname {cont} (q).}$$

ความสัมพันธ์ในส่วนก่อนหน้านี้บ่งบอกถึงความสัมพันธ์ที่แน่นแฟ้นระหว่าง GCD ในR [ X ]และในF [ X ]เพื่อหลีกเลี่ยงความกำกวม ในส่วนต่อไปนี้ สัญลักษณ์ " gcd " จะถูกจัดทำดัชนีโดยวงแหวนที่คำนวณ GCD

ถ้าq ₁และq ₂อยู่ในF [ X ]แล้ว $${\displaystyle \operatorname {primpart} (\gcd _{F[X]}(q_{1},q_{2}))=\gcd _{R[X]}(\operatorname {primpart} (q_{1}),\operatorname {primpart} (q_{2})).}$$

ถ้าp ₁และp ₂อยู่ใน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 ]

สำหรับพหุนามตัวแปรเดียวบนจำนวนตรรกยะ อาจคิดว่าอัลกอริทึมของยูคลิดเป็นวิธีที่สะดวกในการคำนวณหา ห.ร.ม. อย่างไรก็ตาม วิธีนี้เกี่ยวข้องกับการลดรูปเศษส่วนของจำนวนเต็มจำนวนมาก และอัลกอริทึมที่ได้นั้นไม่มีประสิทธิภาพ ด้วยเหตุนี้ จึงได้มีการออกแบบวิธีการปรับเปลี่ยนอัลกอริทึมของยูคลิดให้ใช้งานได้เฉพาะกับพหุนามบนจำนวนเต็มเท่านั้น วิธีการเหล่านี้ประกอบด้วยการแทนที่การหารแบบยูคลิดซึ่งทำให้เกิดเศษส่วน ด้วยการหารเทียมและการแทนที่ลำดับเศษเหลือของอัลกอริทึมของยูคลิดด้วยลำดับเศษเหลือเทียม (ดูด้านล่าง )

ในส่วนก่อนหน้านี้ เราได้เห็นแล้วว่า ตัวหารร่วมมาก (GCD) ของพหุนามในR [ X ]สามารถอนุมานได้จาก GCD ในRและในF [ X ]การพิจารณาอย่างละเอียดในบทพิสูจน์แสดงให้เห็นว่า วิธีนี้ช่วยให้เราพิสูจน์การมีอยู่ของ GCD ในR [ X ] ได้ หาก GCD เหล่านั้นมีอยู่ในRและในF [ X ]โดยเฉพาะอย่างยิ่ง หาก GCD มีอยู่ในRและหากXถูกลดเหลือตัวแปรเดียว วิธีนี้จะพิสูจน์ได้ว่า GCD มีอยู่ในR [ X ] (อัลกอริทึมของยูคลิดพิสูจน์การมีอยู่ของ GCD ในF [ X ] )

พหุนามใน ตัวแปร nตัว อาจถือได้ว่าเป็นพหุนามเอกตัวแปรบนวงแหวนของพหุนามในตัวแปร ( n − 1 ) ตัว ดังนั้น การเวียนเกิดเกี่ยวกับจำนวนตัวแปรแสดงให้เห็นว่า ถ้าตัวหารร่วมมาก (GCD) มีอยู่และสามารถคำนวณได้ในRแล้ว ตัวหารร่วมมากก็จะมีอยู่และสามารถคำนวณได้ในทุกวงแหวนพหุนามหลายตัวแปรบนRโดยเฉพาะอย่างยิ่ง ถ้าRเป็นวงแหวนของจำนวนเต็มหรือฟิลด์ ตัวหารร่วมมากก็จะมีอยู่ในR [ x₁ , ..., xₙ ] และสิ่งที่จะกล่าวต่อไป _นี้เป็นอัลกอริทึมในการคำนวณตัวหารร่วมมากเหล่า _นั้น

การพิสูจน์ว่าวงแหวนพหุนามเหนือโดเมนการแยกตัวประกอบที่ไม่ซ้ำกันก็เป็นโดเมนการแยกตัวประกอบที่ไม่ซ้ำกันเช่นกันนั้นคล้ายกัน แต่ไม่ได้ให้ขั้นตอนวิธี เนื่องจากไม่มีขั้นตอนวิธีทั่วไปในการแยกตัวประกอบพหุนามตัวแปรเดียวเหนือฟิลด์ (มีตัวอย่างของฟิลด์ที่ไม่มีขั้นตอนวิธีแยกตัวประกอบสำหรับพหุนามตัวแปรเดียว)

ในส่วนนี้ เราจะพิจารณาโดเมนเชิงจำนวนเต็มZ (โดยทั่วไปคือวงแหวนZของจำนวนเต็ม) และฟิลด์เศษส่วนQ ของมัน (โดยทั่วไปคือฟิลด์Qของจำนวนตรรกยะ) เมื่อกำหนดพหุนามสองตัวAและBในวงแหวนพหุนามเอกตัวแปรZ [ X ]การหารแบบยุคลิด (เหนือQ ) ของAด้วยBจะให้ผลหารและเศษเหลือซึ่งอาจไม่อยู่ใน Z [ X ]

เพราะหากนำอัลกอริทึมของยูคลิดมาใช้กับพหุนามต่อไปนี้^{[ 2 ]} และ เศษที่เหลือของอัลกอริทึมของยูคลิดที่ต่อเนื่องกัน จะ เห็นได้ว่าแม้จะมีดีกรีน้อยและขนาดของสัมประสิทธิ์ของพหุนามอินพุตเล็ก แต่ก็ต้องจัดการและลดทอนเศษส่วนจำนวนเต็มที่มีขนาดค่อนข้างใหญ่ $${\displaystyle X^{8}+X^{6}-3X^{4}-3X^{3}+8X^{2}+2X-5}$$$${\displaystyle 3X^{6}+5X^{4}-4X^{2}-9X+21,}$$$${\displaystyle {\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 ]

ถ้าและและa ≥ bเศษเหลือเสมือนของการหารเสมือนของAด้วยBซึ่งแสดงด้วยprem( A , B )คือ โดยที่lc( B )คือสัมประสิทธิ์นำของB (สัมประสิทธิ์ของX ^b ) ${\displaystyle \deg(A)=a}$${\displaystyle \deg(B)=b}$$${\displaystyle \operatorname {prem} (A,B)=\operatorname {rem} (\operatorname {lc} (B)^{a-b+1}A,B),}$$

เศษเหลือเทียมของการหารเทียมของพหุนามสองตัวในZ [ X ]จะเป็นของZ [ X ] เสมอ

ลำดับเศษเหลือเทียม (pseudo-remainder sequence)คือลำดับของเศษเหลือ (เทียม) r _iที่ได้จากการแทนที่คำสั่ง ของอัลกอริทึมของยูคลิดด้วย โดย ที่αเป็นสมาชิกของZที่หารสัมประสิทธิ์ของตัวเศษทุกตัวลงตัวพอดี การเลือกค่าα ที่แตกต่างกัน จะให้ลำดับเศษเหลือเทียมที่แตกต่างกัน ซึ่งจะอธิบายในหัวข้อถัดไป $${\displaystyle r_{i+1}:=\operatorname {rem} (r_{i-1},r_{i})}$$$${\displaystyle r_{i+1}:={\frac {\operatorname {prem} (r_{i-1},r_{i})}{\alpha }},}$$

เนื่องจากตัวหารร่วมของพหุนามสองตัวจะไม่เปลี่ยนแปลงหากพหุนามเหล่านั้นถูกคูณด้วยค่าคงที่ที่ผกผันได้ (ในQ ) ดังนั้นพจน์ที่ไม่เป็นศูนย์ตัวสุดท้ายในลำดับเศษเหลือเทียมจึงเป็นตัวหารร่วมมาก (ในQ [ X ] ) ของพหุนามที่ป้อนเข้ามา ด้วยเหตุนี้ ลำดับเศษเหลือเทียมจึงช่วยให้สามารถคำนวณตัวหารร่วมมากในQ [ X ] ได้ โดยไม่ต้องใช้เศษส่วนใน Q

ในบางบริบท จำเป็นอย่างยิ่งที่จะต้องควบคุมเครื่องหมายของสัมประสิทธิ์นำหน้าของเศษเหลือเทียม โดยทั่วไปแล้วจะเป็นกรณีเมื่อคำนวณผลลัพธ์และผลลัพธ์ย่อยหรือสำหรับการใช้ทฤษฎีบทของสเติร์มการควบคุมนี้สามารถทำได้โดยการแทนที่lc( B )ด้วยค่าสัมบูรณ์ในนิยามของเศษเหลือเทียม หรือโดยการควบคุมเครื่องหมายของα (ถ้าαหารสัมประสิทธิ์ทั้งหมดของเศษเหลือลงตัว ก็จะเป็นจริงเช่นเดียวกัน^{สำหรับ} −α ) ^{[ 1} ]

ลำดับเศษเหลือที่ง่ายที่สุด (ในการกำหนด) คือการเลือกα = 1 เสมอ ในทางปฏิบัติแล้ว วิธีนี้ไม่น่าสนใจนัก เนื่องจากขนาดของสัมประสิทธิ์จะเพิ่มขึ้นแบบทวีคูณตามดีกรีของพหุนามที่ป้อนเข้ามา สิ่งนี้ปรากฏให้เห็นอย่างชัดเจนในตัวอย่างในส่วนก่อนหน้า ซึ่งเศษเหลือเทียมที่ต่อเนื่องกันคือ จำนวนหลักของสัมประสิทธิ์ของเศษเหลือเทียมที่ต่อเนื่องกันจะเพิ่มขึ้นมากกว่าสองเท่าในแต่ละรอบของการทำงานของอัลกอริทึม นี่คือพฤติกรรมทั่วไปของลำดับเศษเหลือเทียมแบบง่ายๆ $${\displaystyle -15\,X^{4}+3\,X^{2}-9,}$$$${\displaystyle 15795\,X^{2}+30375\,X-59535,}$$$${\displaystyle 1254542875143750\,X-1654608338437500,}$$$${\displaystyle 12593338795500743100931141992187500.}$$

ลำดับเศษเหลือเทียมแบบดั้งเดิมประกอบด้วยการเลือกค่าα ให้ เป็นเนื้อหาของตัวเศษ ดังนั้น พหุนาม r _i ทั้งหมด จึงเป็นพหุนามแบบดั้งเดิม

ลำดับเศษเหลือเทียมแบบดั้งเดิมคือลำดับเศษเหลือเทียมที่สร้างสัมประสิทธิ์ที่เล็กที่สุด อย่างไรก็ตาม จำเป็นต้องคำนวณตัวหารร่วมมากจำนวนมากในZดังนั้นจึงไม่มีประสิทธิภาพเพียงพอที่จะใช้ในทางปฏิบัติ โดยเฉพาะอย่างยิ่งเมื่อZเป็นวงแหวนพหุนามเอง

ด้วยข้อมูลป้อนเข้าชุดเดียวกับในส่วนก่อนหน้า เศษที่เหลือจากการหารด้วยเนื้อหาของมันคือ ขนาดเล็กของสัมประสิทธิ์ทำให้มองไม่เห็นข้อเท็จจริงที่ว่ามีการคำนวณตัวหารร่วมมาก (GCD) ของจำนวนเต็มจำนวนมากและการหารด้วย GCD $${\displaystyle -5\,X^{4}+X^{2}-3,}$$$${\displaystyle 13\,X^{2}+25\,X-49,}$$$${\displaystyle 4663\,X-6150,}$$$${\displaystyle 1.}$$

ลำดับผลลัพธ์ย่อยสามารถคำนวณได้โดยใช้เศษเหลือเทียมเช่นกัน กระบวนการนี้ประกอบด้วยการเลือกαในลักษณะที่r _i ทุกตัว เป็นพหุนามผลลัพธ์ย่อย ที่น่าประหลาดใจคือ การคำนวณαนั้นง่ายมาก (ดูด้านล่าง) ในทางกลับกัน การพิสูจน์ความถูกต้องของอัลกอริทึมนั้นยาก เนื่องจากต้องคำนึงถึงความเป็นไปได้ทั้งหมดสำหรับความแตกต่างของดีกรีของเศษเหลือสองตัวที่อยู่ติดกัน

สัมประสิทธิ์ในลำดับผลลัพธ์ย่อยมักจะไม่มากไปกว่าสัมประสิทธิ์ในลำดับเศษเหลือเทียมดั้งเดิม เนื่องจากไม่จำเป็นต้อง คำนวณ GCD ใน Z ดังนั้นลำดับผลลัพธ์ย่อยที่มีเศษเหลือเทียมจึงให้การคำนวณที่มีประสิทธิภาพที่สุด

ด้วยข้อมูลป้อนเข้าชุดเดียวกับในส่วนก่อนหน้า เศษที่เหลือที่ได้จะเป็นดังนี้ สัมประสิทธิ์มีขนาดที่เหมาะสม ได้มาโดยไม่ต้องคำนวณตัวหารร่วมมาก (GCD) แต่ใช้เพียงการหารที่ตรงกันเท่านั้น ทำให้ขั้นตอนวิธีนี้มีประสิทธิภาพมากกว่าลำดับเศษเหลือเทียมแบบดั้งเดิม $${\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] rᵢคือเศษเหลือเทียมที่ต่อเนื่องกันใน Z [ X ]ตัวแปรiและ dᵢ เป็นจำนวนเต็มที่ไม่เป็นลบ และอักษรกรีกแทนองค์ประกอบในZฟังก์ชันและแทนดีกรีของพหุนาม และเศษเหลือของการหาร _แบบยุคลิด ในอัลกอริทึมนี้ เศษเหลือนี้จะอยู่ในZ [ X ] เสมอ สุดท้าย การหารที่แสดงด้วย / จะเป็นการ หาร ที่แม่นยำเสมอ และผลลัพธ์จะอยู่ในZ [ X ]หรือในZdeg()rem()

r ₀  := a r ₁  := b สำหรับ ( i  := 1; r _i ≠ 0; i  := i +1) ทำ

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" ย่อมาจาก leading coefficient ซึ่งเป็นสัมประสิทธิ์ที่มีดีกรีสูงสุดของตัวแปร

อัลกอริทึมนี้ไม่เพียงแต่คำนวณตัวหารร่วมมาก ( 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 พหุ นามผลลัพธ์ย่อยอื่นๆ ทั้งหมดเป็นศูนย์

เราสามารถใช้เศษเหลือเทียมในการสร้างลำดับที่มีคุณสมบัติเช่นเดียวกับลำดับสเติร์มได้ ซึ่งจำเป็นต้องควบคุมเครื่องหมายของเศษเหลือเทียมที่ต่อเนื่องกัน เพื่อให้มีเครื่องหมายเดียวกันกับในลำดับสเติร์ม ซึ่งสามารถทำได้โดยการกำหนดเศษเหลือเทียมที่ดัดแปลงแล้วดังต่อไปนี้

ถ้าและและa ≥ bค่าเศษเหลือเทียมที่แก้ไขแล้วprem2( A , B )ของการหารเทียมของAด้วยBคือ โดยที่| lc( B ) |คือค่าสัมบูรณ์ของสัมประสิทธิ์นำหน้าของB (สัมประสิทธิ์ของX ^b ) ${\displaystyle \deg(A)=a}$${\displaystyle \deg(B)=b}$$${\displaystyle \operatorname {prem2} (A,B)=-\operatorname {rem} (\left|\operatorname {lc} (B)\right|^{a-b+1}A,B),}$$

สำหรับพหุนามอินพุตที่มีสัมประสิทธิ์เป็นจำนวนเต็ม วิธีนี้ช่วยให้สามารถดึงลำดับสเติร์มที่ประกอบด้วยพหุนามที่มีสัมประสิทธิ์เป็นจำนวนเต็มได้ ลำดับเศษเหลือเทียมที่เป็นผลลัพธ์ย่อยอาจถูกปรับเปลี่ยนในทำนองเดียวกัน ซึ่งในกรณีนี้เครื่องหมายของเศษเหลือจะตรงกับเครื่องหมายที่คำนวณจากจำนวนตรรกยะ

โปรดทราบว่าอัลกอริทึมสำหรับการคำนวณลำดับเศษเหลือเทียมของผลลัพธ์ย่อยที่ระบุไว้ข้างต้นจะคำนวณพหุนามผลลัพธ์ย่อยที่ไม่ถูกต้องหากใช้แทนที่จะใช้ ${\displaystyle -\mathrm {prem2} (A,B)}$${\displaystyle \operatorname {prem} (A,B)}$

ถ้าfและgเป็นพหุนามในF [ x ]สำหรับฟิลด์F ที่สร้างขึ้นอย่างจำกัด อัลกอริทึมยุคลิดเป็นวิธีที่เป็นธรรมชาติที่สุดในการคำนวณหา ห.ร.ม. ของพหุนามเหล่านั้น อย่างไรก็ตาม ระบบ พีชคณิตคอมพิวเตอร์ สมัยใหม่ จะใช้อัลกอริทึมนี้เฉพาะในกรณีที่Fเป็นฟิลด์จำกัดเท่านั้น เนื่องจากปรากฏการณ์ที่เรียกว่าการขยายตัวของนิพจน์ระดับกลางแม้ว่าดีกรีจะลดลงเรื่อยๆ ในระหว่างอัลกอริทึมยุคลิด แต่ถ้าFไม่ใช่ฟิลด์จำกัดขนาดบิตของพหุนามอาจเพิ่มขึ้น (บางครั้งเพิ่มขึ้นอย่างมาก) ในระหว่างการคำนวณ เนื่องจากการดำเนินการทางคณิตศาสตร์ซ้ำๆ ในF มี ^{แนวโน้ม}ที่จะนำไปสู่นิพจน์ที่ใหญ่ขึ้น ตัวอย่างเช่น การบวกจำนวนตรรกยะสองจำนวนที่มีตัวส่วนจำกัดด้วยbจะนำไปสู่จำนวนตรรกยะที่มีตัวส่วนจำกัดด้วยb²ดังนั้นในกรณีที่เลวร้ายที่สุด ขนาดบิตอาจเพิ่มขึ้นเกือบสองเท่าด้วยการดำเนินการเพียงครั้งเดียว

เพื่อเร่งการคำนวณ ให้ใช้ริงDซึ่งfและgอยู่ในD [ x ]และใช้ไอเดียลIที่D / Iเป็นริงจำกัด จากนั้นคำนวณ GCD เหนือริงจำกัดนี้ด้วยอัลกอริธึมยุคลิด การใช้เทคนิคการสร้างใหม่ ( ทฤษฎีบทเศษเหลือของจีนการสร้างใหม่เชิงตรรกะฯลฯ) สามารถกู้คืน GCD ของfและgจากภาพโมดูลัสจำนวนไอเดียล Iได้ สามารถพิสูจน์ได้^{[ 3 ]}ว่าวิธีนี้ใช้ได้ผลก็ต่อเมื่อละทิ้งภาพโมดูลัสที่มีดีกรีไม่ต่ำสุด และหลีกเลี่ยงไอเดีย ล Iโมดูลัสที่สัมประสิทธิ์นำหน้าเป็นศูนย์

สมมติว่า, , และถ้าเราเลือกแล้วจะเป็นวงแหวนจำกัด (ไม่ใช่ฟิลด์เนื่องจากไม่ใช่ค่าสูงสุดใน) อัลกอริทึมแบบยุคลิดที่ใช้กับภาพของในสำเร็จและส่งคืนค่า 1 ซึ่งหมายความว่า ตัวหารร่วมมาก (GCD) ของในต้องเป็น 1 เช่นกัน โปรดทราบว่าตัวอย่างนี้สามารถจัดการได้ง่ายด้วยวิธีใดก็ได้ เนื่องจากดีกรีมีขนาดเล็กเกินไปที่จะเกิดการขยายตัวของนิพจน์ แต่แสดงให้เห็นว่าถ้าพหุนามสองตัวมี GCD เท่ากับ 1 อัลกอริทึมแบบมอดูลาร์มีแนวโน้มที่จะหยุดทำงานหลังจากไอเดียลเดียว ${\displaystyle F=\mathbb {Q} ({\sqrt {3}})}$${\displaystyle D=\mathbb {Z} [{\sqrt {3}}]}$${\displaystyle f={\sqrt {3}}x^{3}-5x^{2}+4x+9}$${\displaystyle g=x^{4}+4x^{2}+3{\sqrt {3}}x-6}$${\displaystyle I=(2)}$${\displaystyle D/I}$${\displaystyle I}$${\displaystyle D}$${\displaystyle f,g}$${\displaystyle (D/I)[x]}$${\displaystyle f,g}$${\displaystyle F[x]}$${\displaystyle I}$

• รายการหัวข้อพหุนาม
• อัลกอริทึมการหารหลายตัวแปร