Polynomial greatest common divisor
বীজগণিতে, দুটি বহুপদীর সর্বাধিক সাধারণ বিভাজক (প্রায়শই জি. সি. ডি হিসাবে সংক্ষিপ্ত করা হয়) হল একটি বহুপদী, যা সর্বোচ্চ সম্ভাব্য মাত্রার, যা দুটি মূল বহুপদীর একটি গুণক। এই ধারণাটি দুটি পূর্ণসংখ্যার সর্বশ্রেষ্ঠ সাধারণ বিভাজকের অনুরূপ। একটি ক্ষেত্রের উপর অভিন্ন বহুপদীর গুরুত্বপূর্ণ ক্ষেত্রে বহুপদী জি. সি. ডি গণনা করা যেতে পারে, যেমন পূর্ণসংখ্যা জি. সি. ডি-র জন্য, দীর্ঘ বিভাজন ব্যবহার করে ইউক্লিডীয় অ্যালগরিদম দ্বারা। বহুপদী জি. সি. ডি শুধুমাত্র একটি বিপরীতমুখী ধ্রুবক দ্বারা গুণন পর্যন্ত সংজ্ঞায়িত করা হয়। পূর্ণসংখ্যা জি. সি. ডি এবং বহুপদী জি. সি. ডি-র মধ্যে সাদৃশ্য ইউক্লিডীয় অ্যালগরিদম এবং ইউক্লিডীয় বিভাগ থেকে অনুমান করা যেতে পারে এমন সমস্ত বৈশিষ্ট্যকে অভিন্ন বহুপদী পর্যন্ত প্রসারিত করার অনুমতি দেয়। অধিকন্তু, বহুপদী জি. সি. ডি-র নির্দিষ্ট বৈশিষ্ট্য রয়েছে যা এটিকে বীজগণিতের বিভিন্ন ক্ষেত্রে একটি মৌলিক ধারণা করে তোলে। সাধারণত, দুটি বহুপদীর জি. সি. ডি-র শিকড় দুটি বহুপদের সাধারণ শিকড়, এবং এটি তাদের গণনা না করেই শিকড় সম্পর্কে তথ্য সরবরাহ করে। উদাহরণস্বরূপ, একটি পলিনোমিয়ালের একাধিক মূল হল পলিনোমিয়ালের জিসিডি এবং তার ডেরিভেটিভের মূল, এবং আরও জিসিডি গণনাগুলি পলিনোমিয়ালের বর্গ-মুক্ত ফ্যাক্টরাইজেশন গণনা করার অনুমতি দেয়, যা পলিনোমিয়াল সরবরাহ করে যার মূলগুলি মূল পলিনোমিয়ালের প্রদত্ত গুণের মূল। সর্বাধিক সাধারণ বিভাজককে সংজ্ঞায়িত করা যেতে পারে এবং বিদ্যমান থাকতে পারে, আরও সাধারণভাবে, একটি ক্ষেত্র বা পূর্ণসংখ্যার বলয়ের উপর মাল্টিভ্যারিয়েট পলিনোমিয়ালের জন্য এবং একটি অনন্য ফ্যাক্টরাইজেশন ডোমেনের উপরও। সহগের রিংয়ে একটি জিসিডি অ্যালগরিদম থাকার সাথে সাথে এগুলি গণনা করার জন্য অ্যালগরিদম রয়েছে। এই অ্যালগরিদমগুলি ইউক্লিডীয় অ্যালগরিদমের একটি ভিন্ন রূপে সমস্যাটি হ্রাস করার জন্য ভেরিয়েবলের সংখ্যার উপর একটি পুনরাবৃত্তির মাধ্যমে এগিয়ে যায়। এগুলি কম্পিউটার বীজগণিতে একটি মৌলিক হাতিয়ার, কারণ কম্পিউটার বীজগণিত পদ্ধতিগুলি ভগ্নাংশগুলিকে সহজ করার জন্য এগুলি পদ্ধতিগতভাবে ব্যবহার করে। বিপরীতভাবে, বহুপদী জি. সি. ডি-র বেশিরভাগ আধুনিক তত্ত্ব কম্পিউটার বীজগণিত ব্যবস্থার দক্ষতার প্রয়োজনীয়তা পূরণের জন্য তৈরি করা হয়েছে। সাধারণ সংজ্ঞা ধরা যাক এবং একটি অবিচ্ছেদ্য ডোমেনে সহগ সহ বহুপদী হতে হবে, সাধারণত একটি ক্ষেত্র বা পূর্ণসংখ্যা। এবং-এর একটি সর্বশ্রেষ্ঠ সাধারণ ভাজক হল একটি বহুপদী যা এবং-কে ভাগ করে এবং এমনভাবে যে প্রতিটি সাধারণ ভাজক এরও ভাগ করে। প্রত্যেক জোড়া বহুপদীর (উভয় শূন্য নয়) একটি জি. সি. ডি থাকে যদি এবং শুধুমাত্র যদি এটি একটি অনন্য ফ্যাক্টরাইজেশন ডোমেন হয়। যদি একটি ক্ষেত্র হয় এবং উভয়ই শূন্য না হয়, তবে একটি বহুপদী একটি সর্বশ্রেষ্ঠ সাধারণ বিভাজক হয় যদি এবং শুধুমাত্র যদি এটি উভয়কে ভাগ করে এবং এই বৈশিষ্ট্যযুক্ত বহুপদগুলির মধ্যে এটির সর্বাধিক ডিগ্রি থাকে। যদি, জিসিডি 0 হয়। যাইহোক, কিছু লেখক মনে করেন যে এই ক্ষেত্রে এটি সংজ্ঞায়িত করা হয়নি। এবং-এর সর্বশ্রেষ্ঠ সাধারণ বিভাজককে সাধারণত চিহ্নিত করা হয় "। সর্বশ্রেষ্ঠ সাধারণ বিভাজক অনন্য নয়ঃ যদি এবং-এর একটি জি. সি. ডি হয়, তবে বহুপদটি অন্য জি. সি. ডি হয় যদি এবং শুধুমাত্র যদি এই ধরনের এবং-এর একটি বিপরীত উপাদান থাকে। অন্য কথায়, জি. সি. ডি একটি বিপরীতমুখী ধ্রুবক দ্বারা গুণন পর্যন্ত অনন্য। পূর্ণসংখ্যার ক্ষেত্রে, এই অনির্দিষ্টতা নিষ্পত্তি করা হয়েছে, জিসিডি হিসাবে, অনন্য যা ধনাত্মক (অন্য একটি আছে, যা এর বিপরীত)। এই ধারণার সঙ্গে, দুটি পূর্ণসংখ্যার জিসিডিও সর্বশ্রেষ্ঠ (স্বাভাবিক ক্রমের জন্য) সাধারণ বিভাজক। যাইহোক, যেহেতু একটি ইন্টিগ্রাল ডোমেনে পলিনোমিয়ালের জন্য কোনও প্রাকৃতিক মোট ক্রম নেই, তাই এখানে কেউ একইভাবে এগিয়ে যেতে পারে না। একটি ক্ষেত্রের অভিন্ন বহুপদের জন্য, অতিরিক্তভাবে জিসিডি-কে মনিক হতে হতে পারে (অর্থাৎ সর্বোচ্চ মাত্রার সহগ হিসাবে 1 থাকতে হবে), তবে আরও সাধারণ ক্ষেত্রে কোনও সাধারণ প্রথা নেই। অতএব, সমতার মতো বা স্বরলিপির সাধারণ অপব্যবহার যা পড়া উচিত "একটি জিসিডি এবং" এবং "এবং এবং হিসাবে জিসিডি একই সেট আছে"। বিশেষত, এর অর্থ হল যে বিপরীতমুখী ধ্রুবকগুলিই একমাত্র সাধারণ বিভাজক। এই ক্ষেত্রে, পূর্ণসংখ্যার ক্ষেত্রে সাদৃশ্য দ্বারা, একটি বলে যে এবং হয়। উপরে বর্ণিত বৈশিষ্ট্য অনুসারে, দুটি বহুপদীর জি. সি. ডি বিদ্যমান থাকে যদি সহগগুলি কোনও ক্ষেত্র, পূর্ণসংখ্যার বলয় বা আরও সাধারণভাবে একটি অনন্য গুণনক্ষেত্রের অন্তর্গত হয়। যদি এবং-এর কোনও সাধারণ বিভাজক থাকে, তবে তাদের জি. সি. ডি-কে ভাগ করে। যে কোনও পলিনোমিয়ালের জন্য। এই বৈশিষ্ট্যটি ইউক্লিডীয় অ্যালগরিদমের প্রমাণের ভিত্তিতে রয়েছে। সহগের বলয়ের যে কোনও বিপরীতমুখী উপাদানের জন্য,। সুতরাং যে কোনও স্কেলারের জন্য যা বিপরীতমুখী। যদি হয়, তাহলে। যদি হয়, তাহলে। দুটি অভিন্ন পলিনোমিয়ালের জন্য এবং একটি ক্ষেত্রের উপর, এমন পলিনোমিয়াল রয়েছে এবং, যা এবং (বেজাউটের আইডেন্টিটি) এর প্রতিটি রৈখিক সংমিশ্রণকে বিভক্ত করে। তিন বা ততোধিক বহুপদের সর্বশ্রেষ্ঠ সাধারণ বিভাজককে দুটি বহুপদের মতো একইভাবে সংজ্ঞায়িত করা যেতে পারে। এটি দুটি বহুপদীর জি. সি. ডি থেকে সনাক্তকরণ দ্বারা পুনরাবৃত্তভাবে গণনা করা যেতে পারেঃ এবং হাতে গণনা করে জি. সি. ডি দুটি বহুপদের সর্বশ্রেষ্ঠ সাধারণ বিভাজক খুঁজে বের করার বিভিন্ন উপায় রয়েছে। এর মধ্যে দুটি হলঃ পলিনোমিয়ালের ফ্যাক্টরাইজেশন, যেখানে প্রতিটি এক্সপ্রেশনের ফ্যাক্টর খুঁজে পাওয়া যায়, তারপর প্রতিটি ফ্যাক্টরের মধ্যে থেকে সকলের দ্বারা ধারণ করা সাধারণ ফ্যাক্টরের সেট নির্বাচন করা হয়। এই পদ্ধতিটি শুধুমাত্র সহজ ক্ষেত্রেই কার্যকর হতে পারে, কারণ ফ্যাক্টরিং সাধারণত সর্বশ্রেষ্ঠ সাধারণ বিভাজক গণনা করার চেয়ে বেশি কঠিন। ইউক্লিডীয় অ্যালগরিদম, যা দুটি সংখ্যার মতো একই পদ্ধতিতে দুটি বহুপদীর জিসিডি খুঁজে বের করতে ব্যবহার করা যেতে পারে। ফ্যাক্টরিং ব্যবহার করে দুটি পলিনোমিয়ালের জি. সি. ডি খুঁজে বের করতে, কেবল দুটি পলিনোমিয়ালকে সম্পূর্ণরূপে ফ্যাক্টর করুন। তারপর, সমস্ত সাধারণ উপাদানের গুণফল নিন। এই পর্যায়ে, আমাদের অপরিহার্যভাবে একটি মনিক বহুপদী নেই, তাই অবশেষে এটিকে একটি মনিক বহুপদীতে পরিণত করার জন্য একটি ধ্রুবক দ্বারা গুণ করুন। এটি দুটি পলিনোমিয়ালের জিসিডি হবে কারণ এতে সমস্ত সাধারণ বিভাজক রয়েছে এবং এটি মনিক। উদাহরণ 1: এবং-এর জি. সি. ডি খুঁজে বের করুন। সুতরাং, তাদের জি. সি. ডি হল। ইউক্লিডীয় অ্যালগরিদম ফ্যাক্টরিং পলিনোমিয়ালগুলি কঠিন হতে পারে, বিশেষত যদি পলিনোমিয়ালগুলির একটি বড় মাত্রা থাকে। ইউক্লিডীয় অ্যালগরিদম এমন একটি পদ্ধতি যা যে কোনও জোড়া বহুপদের জন্য কাজ করে। এটি ইউক্লিডীয় বিভাজনের বারবার ব্যবহার করে। দুটি সংখ্যার উপর এই অ্যালগরিদম ব্যবহার করার সময়, প্রতিটি পর্যায়ে সংখ্যার আকার হ্রাস পায়। পলিনোমিয়ালের ক্ষেত্রে, প্রতিটি পর্যায়ে পলিনোমিয়ালের মাত্রা হ্রাস পায়। শেষ অ-শূন্য অবশিষ্টাংশ, যা প্রয়োজন হলে মনিক করা হয়, তা হল দুটি বহুপদের জিসিডি। আরও সুনির্দিষ্টভাবে, দুটি বহুপদীর জি. সি. ডি খুঁজে বের করার জন্য এবং, কেউ অনুমান করতে পারে (অন্যথায়, জি. সি. ডি হল), এবং ইউক্লিডীয় বিভাগ দুটি বহুপদ প্রদান করে, ভাগফল এবং, অবশিষ্টাংশ এমন যে একটি বহুপদ উভয়কে বিভক্ত করে এবং যদি এবং শুধুমাত্র যদি এটি উভয়কে এবং ভাগ করে। এইভাবে সেটিং করলে নতুন পলিনোমিয়াল ইত্যাদি পেতে ইউক্লিডীয় বিভাগের পুনরাবৃত্তি করা যেতে পারে। প্রতিটি পর্যায়ে আমাদের আছে তাই ক্রমটি অবশেষে এমন একটি বিন্দুতে পৌঁছাবে যেখানে একজন জি. সি. ডি পেয়েছেঃ উদাহরণস্বরূপঃ এর জি. সি. ডি খুঁজে বের করা এবংঃ যেহেতু শেষ অ-শূন্য অবশিষ্টাংশ, এটি মূল বহুপদের একটি জি. সি. ডি, এবং মনিক জি. সি. ডি হল। এই উদাহরণে, দ্বিতীয় ধাপের আগে 12 টি ফ্যাক্টর করে হরের প্রবর্তন এড়ানো কঠিন নয়। এটি সর্বদা ছদ্ম-অবশিষ্ট ক্রম ব্যবহার করে করা যেতে পারে, তবে, যত্ন ছাড়াই, এটি গণনার সময় খুব বড় পূর্ণসংখ্যা প্রবর্তন করতে পারে। অতএব, কম্পিউটার গণনার জন্য, অন্যান্য অ্যালগরিদম ব্যবহার করা হয়, যা নীচে বর্ণনা করা হয়েছে। এই পদ্ধতিটি তখনই কাজ করে যখন গণনার সময় ঘটে যাওয়া সহগের শূন্যের সমতা পরীক্ষা করা যায়। সুতরাং, বাস্তবে, সহগগুলি অবশ্যই পূর্ণসংখ্যা, মূলদ সংখ্যা, একটি সীমাবদ্ধ ক্ষেত্রের উপাদান হতে হবে, অথবা পূর্ববর্তী ক্ষেত্রগুলির মধ্যে একটির নির্দিষ্টভাবে উত্পন্ন ক্ষেত্র সম্প্রসারণের অন্তর্গত হতে হবে। যদি সহগগুলি ভাসমান-বিন্দু সংখ্যা হয় যা প্রকৃত সংখ্যার প্রতিনিধিত্ব করে যা কেবল আনুমানিকভাবে জানা যায়, তবে একজনকে অবশ্যই একটি সুনির্দিষ্ট গণনার ফলাফলের জন্য জি. সি. ডি-র ডিগ্রি জানতে হবে (এটি একটি সংখ্যাসূচকভাবে স্থিতিশীল ফলাফল; এই ক্ষেত্রে অন্যান্য কৌশল ব্যবহার করা যেতে পারে, সাধারণত একক মান পচনের উপর ভিত্তি করে। একটি ক্ষেত্রে সহগ সহ অভিন্ন বহুপদ একটি ক্ষেত্রের উপর অভিন্ন বহুপদের ক্ষেত্রে বিভিন্ন কারণে বিশেষভাবে গুরুত্বপূর্ণ। প্রথমত, এটি সবচেয়ে প্রাথমিক কেস এবং তাই বীজগণিতের বেশিরভাগ প্রথম কোর্সে উপস্থিত হয়। দ্বিতীয়ত, এটি পূর্ণসংখ্যার ক্ষেত্রে খুব অনুরূপ, এবং এই উপমা ইউক্লিডীয় ক্ষেত্রের ধারণার উৎস। তৃতীয় কারণটি হল মাল্টিভ্যারিয়েট কেস এবং একটি অনন্য ফ্যাক্টরাইজেশন ডোমেনের সহগের জন্য তত্ত্ব এবং অ্যালগরিদমগুলি দৃঢ়ভাবে এই নির্দিষ্ট কেসের উপর ভিত্তি করে। সর্বশেষে, পলিনোমিয়াল জি. সি. ডি অ্যালগরিদম এবং ডিরাইভড অ্যালগরিদমগুলি গণনা না করেই পলিনোমিয়ালের মূল সম্পর্কে দরকারী তথ্য পেতে সহায়তা করে। ইউক্লিডীয় বিভাগ বহুপদগুলির ইউক্লিডীয় বিভাগ, যা জি. সি. ডি গণনার জন্য ইউক্লিডের অ্যালগরিদমে ব্যবহৃত হয়, পূর্ণসংখ্যার ইউক্লিডীয় বিভাগের সাথে খুব মিল। এর অস্তিত্ব নিম্নলিখিত উপপাদ্যের উপর ভিত্তি করেঃ একটি ক্ষেত্রের উপর সংজ্ঞায়িত দুটি অভিন্ন বহুপদী a এবং b ≤ 0 দেওয়া হলে, দুটি বহুপদী q (ভাগফল) এবং r (অবশিষ্টাংশ) বিদ্যমান থাকে যা সন্তুষ্ট করে এবং যেখানে "ডিগ্রি (.)" ডিগ্রি বোঝায় এবং শূন্য বহুপদের ডিগ্রি ঋণাত্মক হিসাবে সংজ্ঞায়িত করা হয়। উপরন্তু, q এবং r এই সম্পর্কগুলির দ্বারা অনন্যভাবে সংজ্ঞায়িত করা হয়। পূর্ণসংখ্যার ইউক্লিডীয় বিভাগ থেকে পার্থক্য হল, পূর্ণসংখ্যার জন্য, ডিগ্রিটি পরম মান দ্বারা প্রতিস্থাপিত হয় এবং স্বতন্ত্রতা পেতে একজনকে ধরে নিতে হবে যে r অ-ঋণাত্মক। যে বলয়গুলির জন্য এই ধরনের উপপাদ্য বিদ্যমান, সেগুলিকে ইউক্লিডীয় ক্ষেত্র বলা হয়। পূর্ণসংখ্যার মতো, বহুপদের ইউক্লিডীয় বিভাজন দীর্ঘ বিভাজন অ্যালগরিদম দ্বারা গণনা করা যেতে পারে। এই অ্যালগরিদমটি সাধারণত কাগজ-এবং-পেন্সিল গণনার জন্য উপস্থাপন করা হয়, তবে এটি কম্পিউটারে ভাল কাজ করে যখন নিম্নরূপ আনুষ্ঠানিক করা হয় (লক্ষ্য করুন যে দীর্ঘ বিভাগের পেন্সিল-এবং-কাগজের গণনায় ভেরিয়েবলগুলির নামগুলি কাগজের শীটের অঞ্চলের সাথে ঠিক মিলে যায়)। নিম্নলিখিত গণনায় "ডিগ" তার যুক্তির মাত্রাকে বোঝায় (প্রচলিত ধারণার সাথে), এবং "এলসি" হল নেতৃস্থানীয় সহগ, যা চলকের সর্বোচ্চ মাত্রার সহগ। এই অ্যালগরিদমের বৈধতার প্রমাণ এই সত্যের উপর নির্ভর করে যে পুরো "ওয়াইল" লুপের সময়, আমাদের একটি অ-ঋণাত্মক পূর্ণসংখ্যা রয়েছে যা প্রতিটি পুনরাবৃত্তিতে হ্রাস পায়। এইভাবে এই অ্যালগরিদমের বৈধতার প্রমাণ ইউক্লিডীয় বিভাগের বৈধতাও প্রমাণ করে। ইউক্লিডের অ্যালগরিদম পূর্ণসংখ্যার ক্ষেত্রে, ইউক্লিডীয় বিভাগ আমাদের জিসিডি গণনার জন্য ইউক্লিডের অ্যালগরিদম সংজ্ঞায়িত করার অনুমতি দেয়। দুটি বহুপদী a এবং b থেকে শুরু করে, ইউক্লিডের অ্যালগরিদমটি পুনরাবৃত্তভাবে জোড়টিকে প্রতিস্থাপন করে (যেখানে "" পূর্ববর্তী বিভাগের অ্যালগরিদম দ্বারা গণনা করা ইউক্লিডীয় বিভাগের অবশিষ্টাংশকে বোঝায়), b = 0 পর্যন্ত। জিসিডি হল শেষ অ-শূন্য অবশিষ্টাংশ। ইউক্লিডের অ্যালগরিদমকে পুনরাবৃত্তিমূলক প্রোগ্রামিং শৈলীতে আনুষ্ঠানিক করা যেতে পারে যেমনঃ অপরিহার্য প্রোগ্রামিং শৈলীতে, একই অ্যালগরিদম হয়ে ওঠে, প্রতিটি মধ্যবর্তী অবশিষ্টাংশকে একটি নাম দেয়ঃ এর ডিগ্রির ক্রম কঠোরভাবে হ্রাস পাচ্ছে। সুতরাং, সর্বাধিক পদক্ষেপের পরে, কেউ একটি শূন্য অবশিষ্টাংশ পায়, ধরুন। যেমন এবং একই বিভাজক রয়েছে, সাধারণ বিভাজকের সেট ইউক্লিডের অ্যালগরিদম দ্বারা পরিবর্তিত হয় না এবং এইভাবে সমস্ত জোড়ার সাধারণ বিভাজকের একই সেট থাকে। এবং এর সাধারণ বিভাজকগুলি এইভাবে এবং 0 এর সাধারণ বিভাজক। সুতরাং এটি এবং এর একটি জি. সি. ডি। এটি কেবল প্রমাণ করে না যে ইউক্লিডের অ্যালগরিদম জিসিডি গণনা করে তবে জিসিডি-র অস্তিত্বও প্রমাণ করে। বেজাউটের পরিচয় এবং বর্ধিত জি. সি. ডি অ্যালগরিদম বেজাউটের পরিচয় একটি জি. সি. ডি সম্পর্কিত উপপাদ্য, যা প্রাথমিকভাবে পূর্ণসংখ্যার জন্য প্রমাণিত, যা প্রতিটি প্রধান আদর্শ ডোমেনের জন্য বৈধ। একটি ক্ষেত্রের উপর অভিন্ন বহুপদের ক্ষেত্রে, এটি নিম্নরূপ বলা যেতে পারে। পলিনোমিয়ালগুলির ক্ষেত্রে এই ফলাফলের আগ্রহ হল যে পলিনোমিয়ালগুলি গণনা করার জন্য একটি দক্ষ অ্যালগরিদম রয়েছে এবং এই অ্যালগরিদমটি ইউক্লিডের অ্যালগরিদম থেকে লুপের প্রতিটি পুনরাবৃত্তিতে করা আরও কয়েকটি গণনার দ্বারা পৃথক। তাই এটিকে এক্সটেন্ডেড জিসিডি অ্যালগরিদম বলা হয়। ইউক্লিডের অ্যালগরিদমের সাথে আরেকটি পার্থক্য হল যে এটি শুধুমাত্র অবশিষ্টাংশের পরিবর্তে ইউক্লিডীয় বিভাগের ভাগফল, চিহ্নিত "কো" ব্যবহার করে। এই অ্যালগরিদমটি নিম্নরূপ কাজ করে। অ্যালগরিদম যে তার আউটপুট নির্দিষ্টকরণকে সন্তুষ্ট করে তার প্রমাণ এই সত্যের উপর নির্ভর করে যে, প্রত্যেকটির জন্য আমাদের পরবর্তী সমতা রয়েছে যা বোঝায় ডিগ্রির উপর দাবিটি এই সত্য থেকে অনুসরণ করে যে, প্রতিটি পুনরাবৃত্তিতে, হ্রাসের মাত্রার সাথে সর্বাধিক ডিগ্রি এবং বৃদ্ধি হয়। এই অ্যালগরিদমের একটি আকর্ষণীয় বৈশিষ্ট্য হল যে, যখন বেজাউটের পরিচয়ের সহগগুলির প্রয়োজন হয়, তখন কেউ তাদের জি. সি. ডি দ্বারা ইনপুট পলিনোমিয়ালগুলির ভাগফল বিনামূল্যে পায়। বীজগাণিতিক সম্প্রসারণের গাণিতিক বর্ধিত জি. সি. ডি অ্যালগরিদমের একটি গুরুত্বপূর্ণ প্রয়োগ হল যে এটি বীজগাণিতিক ক্ষেত্র সম্প্রসারণে বিভাজন গণনা করার অনুমতি দেয়। একটি ক্ষেত্রের বীজগাণিতিক সম্প্রসারণ ধরা যাক, যা এমন একটি উপাদান দ্বারা উৎপন্ন হয় যার ন্যূনতম বহুপদের ডিগ্রি থাকে। এর উপাদানগুলি সাধারণত এর চেয়ে কম মাত্রায় অভিন্ন বহুপদী দ্বারা প্রতিনিধিত্ব করা হয়। যোগ হল কেবল বহুপদগুলির সংযোজনঃ এর গুণ হল বহুপদগুলির গুণ এবং তারপরে এই দ্বারা ভাগ করা হয়ঃ একটি অ-শূন্য উপাদানের বিপরীত হল বেজাউটের পরিচয়ের সহগ, যা বর্ধিত জিসিডি অ্যালগরিদম দ্বারা গণনা করা যেতে পারে। (জিসিডি হল 1 কারণ ন্যূনতম বহুপদীটি অপরিবর্তনীয়)। বর্ধিত জিসিডি অ্যালগরিদমের নির্দিষ্টকরণে ডিগ্রি বৈষম্য দেখায় যে ডিগ () <ডিগ () পেতে আরও বিভাজনের প্রয়োজন নেই। একক পরিবর্তনশীল বহুপদীর ক্ষেত্রে, সর্বশ্রেষ্ঠ সাধারণ বিভাজক এবং ফলস্বরূপের মধ্যে একটি দৃঢ় সম্পর্ক রয়েছে। আরও সুনির্দিষ্টভাবে বলতে গেলে, দুটি বহুপদী পি, কিউ-এর ফলাফল হল পি এবং কিউ-এর সহগগুলির একটি বহুপদী ফাংশন যার মান শূন্য হয় যদি এবং শুধুমাত্র পি এবং কিউ-এর জিসিডি ধ্রুবক না হয়। উপ-ফলাফল তত্ত্ব হল এই বৈশিষ্ট্যের একটি সাধারণীকরণ যা দুটি বহুপদীর সাধারণভাবে জি. সি. ডি-কে চিহ্নিত করার অনুমতি দেয় এবং ফলাফল হল 0-তম উপ-ফলাফল বহুপদী। দুটি বহুপদী পি এবং কিউ-এর আই-তম উপ-ফলস্বরূপ বহুপদী সি (পি, কিউ) সর্বাধিক আই-এর একটি বহুপদী যার সহগগুলি পি এবং কিউ-এর সহগগুলির বহুপদী ফাংশন এবং আই-তম প্রধান উপ-ফলস্বরূপ সহগ সি (পি, কিউ) হল সি (পি, কিউ)-এর ডিগ্রি আই-এর সহগ। তাদের এই বৈশিষ্ট্য রয়েছে যে পি এবং কিউ-এর জিসিডি-র একটি ডিগ্রি ডি রয়েছে যদি এবং শুধুমাত্র যদি। এই ক্ষেত্রে, এসডি (পি, কিউ) হল পি এবং কিউ-এর একটি জিসিডি এবং উপ-ফলস্বরূপ পলিনোমিয়ালগুলির প্রতিটি সহগকে পি এবং কিউ-এর সিলভেস্টার ম্যাট্রিক্সের একটি সাবম্যাট্রিক্সের নির্ধারক হিসাবে সংজ্ঞায়িত করা হয়। এটি বোঝায় যে উপ-ফলাফলগুলি ভালভাবে "বিশেষজ্ঞ" হয়। আরও সুনির্দিষ্টভাবে বলতে গেলে, যে কোনও বিনিময়যোগ্য বলয় আর-এর উপর বহুপদগুলির জন্য উপ-ফলাফলগুলি সংজ্ঞায়িত করা হয় এবং এর নিম্নলিখিত বৈশিষ্ট্য রয়েছে। ধরা যাক φ হল R-এর আরেকটি বিনিময়যোগ্য বলয় S-এর একটি বলয় সমরূপতা। এটি আরেকটি সমরূপতা পর্যন্ত প্রসারিত, যা R এবং S-এর উপর বহুপদী বলয়ের মধ্যেও φ-কে নির্দেশ করে। তারপর, যদি P এবং Q হল R-এর সহগ সহ অভিন্ন বহুপদী হয় এবং তারপর উপ-ফলস্বরূপ বহুপদী এবং φ (P) এবং φ (Q)-এর প্রধান উপ-ফলস্বরূপ সহগগুলি হল P এবং Q-এর φ দ্বারা অঙ্কিত চিত্র। উপ-ফলাফলগুলির দুটি গুরুত্বপূর্ণ বৈশিষ্ট্য রয়েছে যা তাদের পূর্ণসংখ্যা সহগ সহ দুটি বহুপদের জিসিডি-র কম্পিউটারে গণনার জন্য মৌলিক করে তোলে। প্রথমত, নির্ধারকদের মাধ্যমে তাদের সংজ্ঞা হ্যাডামার্ড বৈষম্যের মাধ্যমে জি. সি. ডি-র সহগের আকারকে সীমাবদ্ধ করার অনুমতি দেয়। দ্বিতীয়ত, এই আবদ্ধতা এবং ভাল বিশেষীকরণের বৈশিষ্ট্য মডুলার গণনা এবং চীনা অবশিষ্ট উপপাদ্যের (নীচে দেখুন) মাধ্যমে পূর্ণসংখ্যা সহ দুটি বহুপদীর জিসিডি গণনা করার অনুমতি দেয়। প্রযুক্তিগত সংজ্ঞা K ক্ষেত্রের সহগ সহ দুটি অভিন্ন বহুপদী ধরা যাক। অ-ঋণাত্মক পূর্ণসংখ্যা i-এর জন্য, যেমন i ≤ m এবং i ≤ n, রৈখিক মানচিত্রটি এমন হতে দিন যাতে P এবং Q-এর ফলস্বরূপ সিলভেস্টার ম্যাট্রিক্সের নির্ধারক হয়, যা X-এর শক্তির ভিত্তিতে (বর্গ) ম্যাট্রিক্স। একইভাবে, আই-সাব-ফলাফল বহুপদকে ম্যাট্রিক্সের সাবম্যাট্রিসের নির্ধারক হিসাবে সংজ্ঞায়িত করা হয়। আসুন আমরা এই ম্যাট্রিক্সগুলি আরও সুনির্দিষ্টভাবে বর্ণনা করি; ধরা যাক আই <0 বা আই> এম-এর জন্য পাই = 0, এবং আই <0 বা আই> এন-এর জন্য কুই = 0। সিলভেস্টার ম্যাট্রিক্স হল (এম + এন) × (এম + এন)-ম্যাট্রিক্স যাতে আই-তম সারি এবং জে-তম কলামের সহগ হল জে ≤ এন-এর জন্য পিএম + জে − আই এবং জে> এন-এর জন্য কিউজে − আইঃ এর ম্যাট্রিক্স টি হল এস-এর (এম + এন − আই) × (এম + এন − 2 আই)-সাবম্যাট্রিক্স যা দ্বারা প্রাপ্ত হয়। প্রধান উপ-ফলাফল সহগ হল টিআই-এর প্রথম সারির m + n − 2i-এর নির্ধারক। ধরা যাক Vi হল (m + n − 2i) × (m + n − i) ম্যাট্রিক্স যা নিম্নরূপ সংজ্ঞায়িত করা হয়েছে। প্রথমে আমরা (m + n − 2i − 1) × (m + n − 2i − 1) আইডেন্টিটি ম্যাট্রিক্সের ডানদিকে শূন্যের (i + 1) কলাম যোগ করি। তারপর আমরা ফলস্বরূপ ম্যাট্রিক্সের নীচের অংশটিকে (m + n − i − 1) শূন্য এবং তারপরে xi, xi − 1,., x, 1 দিয়ে গঠিত একটি সারি দ্বারা সীমানা করিঃ এই স্বরলিপির সাথে, i-তম উপ-ফলাফল বহুপদী ম্যাট্রিক্স পণ্য viti-এর নির্ধারক। এর ডিগ্রি জে এর সহগ হল এম + এন − 2আই − 1 প্রথম সারিতে এবং (এম + এন − আই − জে)-তম সারিতে গঠিত টিআই-এর বর্গ উপ-ম্যাট্রিক্সের নির্ধারক। প্রমাণের রেখাচিত্র এটি স্পষ্ট নয় যে, সংজ্ঞায়িত হিসাবে, উপ-ফলাফলগুলির কাঙ্ক্ষিত বৈশিষ্ট্য রয়েছে। তা সত্ত্বেও, রৈখিক বীজগণিত এবং বহুপদের বৈশিষ্ট্যগুলি যদি একসাথে রাখা হয় তবে প্রমাণটি বেশ সহজ। সংজ্ঞায়িত হিসাবে, ম্যাট্রিক্স টিআই-এর কলামগুলি এর চিত্রের অন্তর্গত কিছু বহুপদের সহগের ভেক্টর। i-তম উপ-ফলস্বরূপ বহুপদী Si-এর সংজ্ঞাটি দেখায় যে তার সহগগুলির ভেক্টর এই কলাম ভেক্টরগুলির একটি রৈখিক সংমিশ্রণ, এবং এইভাবে যে Si এর চিত্রের অন্তর্গত যদি GCD-র ডিগ্রি i-এর চেয়ে বেশি হয়, তবে বেজাউটের পরিচয় দেখায় যে এর চিত্রের প্রতিটি অ-শূন্য বহুপদীর ডিগ্রি i-এর চেয়ে বড়। এর অর্থ হল যে সি = 0। অন্যদিকে, যদি জি. সি. ডি-র মাত্রা i হয়, তাহলে বেজাউটের পরিচয় আবার প্রমাণ করে যে জি. সি. ডি-র যে গুণিতকগুলি এম + এন-আই-এর চেয়ে কম ডিগ্রি রয়েছে সেগুলি এর প্রতিচ্ছবিতে রয়েছে। এই গুণকগুলির ভেক্টর স্থানের মাত্রা m + n − 2i এবং জোড়ার দিক থেকে বিভিন্ন মাত্রার বহুপদের একটি ভিত্তি রয়েছে, যা i এর চেয়ে ছোট নয়। এর থেকে বোঝা যায় যে, এম + এন − 2আই-এর সাবম্যাট্রিক্সটি হল আইডেন্টিটি ম্যাট্রিক্স এবং এইভাবে এসআই 0 নয়। সুতরাং চিত্রের মধ্যে সি একটি বহুপদী, যা জি. সি. ডি-র একটি গুণিতক এবং এর মাত্রা একই। সুতরাং এটি একটি সর্বশ্রেষ্ঠ সাধারণ বিভাজক। জিসিডি এবং রুট ফাইন্ডিং স্কোয়ার-ফ্রি ফ্যাক্টরাইজেশন বেশিরভাগ রুট-ফাইন্ডিং অ্যালগরিদম একাধিক মূলযুক্ত পলিনোমিয়ালের সাথে খারাপ আচরণ করে। তাই রুট-ফাইন্ডিং অ্যালগরিদম কল করার আগে এগুলি সনাক্ত করা এবং অপসারণ করা দরকারী। একটি জিসিডি গণনা একাধিক মূলের অস্তিত্ব সনাক্ত করার অনুমতি দেয়, যেহেতু একটি বহুপদের একাধিক মূল হল বহুপদের জিসিডি এবং তার ব্যুৎপত্তিগত মূল। পলিনোমিয়ালের জিসিডি এবং তার ডেরিভেটিভ গণনা করার পরে, আরও জিসিডি গণনাগুলি পলিনোমিয়ালের সম্পূর্ণ বর্গ-মুক্ত ফ্যাক্টরাইজেশন প্রদান করে, যা একটি ফ্যাক্টরাইজেশন যেখানে, প্রতিটি আই-এর জন্য, পলিনোমিয়াল ফাই হয় 1 হয় যদি f-এর গুণিতক i-এর কোনও মূল না থাকে বা একটি বর্গ-মুক্ত পলিনোমিয়াল (যা একাধিক মূল ছাড়া একটি পলিনোমিয়াল) যার মূলগুলি ঠিক f-এর গুণিতক i-এর মূল (ইউন-এর অ্যালগরিদম দেখুন)। এইভাবে বর্গ-মুক্ত ফ্যাক্টরাইজেশন একাধিক মূল সহ একটি বহুপদের মূল-সন্ধানকে নিম্ন মাত্রার বেশ কয়েকটি বর্গ-মুক্ত বহুপদের মূল-অনুসন্ধানে হ্রাস করে। বর্গ-মুক্ত ফ্যাক্টরাইজেশন বেশিরভাগ পলিনোমিয়াল ফ্যাক্টরাইজেশন অ্যালগরিদমের প্রথম ধাপ। স্টর্ম সিকোয়েন্স বাস্তব সহগ সহ একটি বহুপদীর স্টর্ম সিকোয়েন্স হল বহুপদী এবং তার ডেরিভেটিভে প্রয়োগ করা ইউক্লিডের অ্যালগরিদমের একটি বৈকল্পিক দ্বারা প্রদত্ত অবশিষ্টাংশের ক্রম। স্টর্ম সিকোয়েন্স পাওয়ার জন্য, ইউক্লিডের অ্যালগরিদমের নির্দেশকে প্রতিস্থাপন করা হয়। ধরা যাক, একটি বিন্দুতে মূল্যায়ন করার সময় V (a) ক্রমানুসারে চিহ্নগুলির পরিবর্তনের সংখ্যা। স্টর্মের উপপাদ্য দাবি করে যে, V (a) − V (b) হল [a, b] ব্যবধানের পলিনোমিয়ালের বাস্তব মূলের সংখ্যা। এইভাবে স্টর্ম ক্রম একটি নির্দিষ্ট বিরতিতে প্রকৃত মূলের সংখ্যা গণনা করার অনুমতি দেয়। প্রতিটি উপ-ব্যবধান সর্বাধিক একটি মূল না হওয়া পর্যন্ত ব্যবধানটিকে উপবিভাগ করে, এটি একটি অ্যালগরিদম সরবরাহ করে যা নির্বিচারে ছোট দৈর্ঘ্যের বিরতিতে প্রকৃত মূলগুলি সনাক্ত করে। একটি বলয় এবং তার ভগ্নাংশের ক্ষেত্রের উপর জিসিডি এই বিভাগে, আমরা একটি অনন্য ফ্যাক্টরাইজেশন ডোমেন আর-এর উপর বহুপদগুলি বিবেচনা করি, সাধারণত পূর্ণসংখ্যার বলয় এবং তার ভগ্নাংশের ক্ষেত্র এফ-এর উপর, সাধারণত মূলদ সংখ্যার ক্ষেত্র, এবং আমরা এই বলয়গুলির উপর চলকগুলির একটি সেটের মধ্যে বহুপদগুলির বলয়গুলি আর [এক্স] এবং এফ [এক্স] বোঝাই। প্রিমিটিভ পার্ট-কন্টেন্ট ফ্যাক্টরাইজেশন একটি পলিনোমিয়ালের বিষয়বস্তু, যা "কন্ট (পি)" হিসাবে চিহ্নিত করা হয়, তার সহগগুলির জিসিডি। একটি বহুপদী q ωF [X] লেখা যেতে পারে যেখানে p ωR [X] এবং c ωR: q (উদাহরণস্বরূপ তাদের গুণফল) এবং p = cq এর সহগের সমস্ত হরের গুণিতক c নেওয়ার জন্য এটি যথেষ্ট। q-এর বিষয়বস্তুকে এভাবে সংজ্ঞায়িত করা হয়ঃ উভয় ক্ষেত্রেই, বিষয়বস্তুকে R-এর একক দ্বারা গুণন পর্যন্ত সংজ্ঞায়িত করা হয়। R [X] বা F [X]-এ একটি বহুপদের আদিম অংশটি দ্বারা সংজ্ঞায়িত করা হয়। উভয় ক্ষেত্রেই, এটি R [X]-এ একটি বহুপদী যা আদিম, যার অর্থ হল যে 1 তার সহগের একটি GCD। সুতরাং R [X] বা F [X]-এর প্রতিটি বহুপদকে ফ্যাক্টরাইজ করা যেতে পারে এবং এই ফ্যাক্টরাইজেশনটি R-এর একটি একক দ্বারা বিষয়বস্তুর গুণন এবং এই ইউনিটের বিপরীত দ্বারা আদিম অংশের গুণন পর্যন্ত অনন্য। গাউসের লেম্মা বোঝায় যে দুটি আদিম বহুপদের গুণফল আদিম। আর এবং এফ-এর উপর জিসিডি-র মধ্যে সম্পর্ক পূর্ববর্তী বিভাগের সম্পর্কগুলি আর [এক্স] এবং এফ [এক্স]-এর মধ্যে জিসিডি-র মধ্যে একটি শক্তিশালী সম্পর্ককে বোঝায়। অস্পষ্টতা এড়ানোর জন্য, "জিসিডি" স্বরলিপিটি নিম্নলিখিত রিং দ্বারা সূচীভুক্ত করা হবে, যেখানে জিসিডি গণনা করা হয়। যদি q1 এবং q2 F [X]-এর অন্তর্গত হয়, তাহলে যদি p1 এবং p2 R [X]-এর অন্তর্গত হয়, তাহলে এবং এইভাবে বহুপদী GCD-র গণনা মূলত F [X] এবং R [X]-এর উপর একই সমস্যা। মূলদ সংখ্যার উপর অভিন্ন বহুপদগুলির জন্য, কেউ ভাবতে পারে যে ইউক্লিডের অ্যালগরিদম জিসিডি গণনা করার জন্য একটি সুবিধাজনক পদ্ধতি। যাইহোক, এটি পূর্ণসংখ্যার ভগ্নাংশ একটি বড় সংখ্যা সরলীকরণ জড়িত, এবং ফলাফল অ্যালগরিদম দক্ষ নয়। এই কারণে, শুধুমাত্র পূর্ণসংখ্যার উপর বহুপদের সাথে কাজ করার জন্য ইউক্লিডের অ্যালগরিদম সংশোধন করার জন্য পদ্ধতিগুলি তৈরি করা হয়েছে। এগুলি ইউক্লিডীয় বিভাগকে প্রতিস্থাপন করে গঠিত, যা একটি তথাকথিত ছদ্ম-বিভাগ দ্বারা ভগ্নাংশ প্রবর্তন করে এবং ইউক্লিডের অ্যালগরিদমের অবশিষ্ট ক্রমকে তথাকথিত ছদ্ম-অবশিষ্ট ক্রম দ্বারা প্রতিস্থাপন করে (নীচে দেখুন)। বহু-বৈকল্পিক বহুপদের জন্য জিসিডি-র অস্তিত্বের প্রমাণ পূর্ববর্তী বিভাগে আমরা দেখেছি যে, আর [এক্স]-এ বহুপদের জিসিডি-কে আর এবং এফ [এক্স]-এ জিসিডি থেকে বের করা যেতে পারে। প্রমাণটি ঘনিষ্ঠভাবে দেখলে দেখা যায় যে এটি আমাদের আর [এক্স]-এ জিসিডি-র অস্তিত্ব প্রমাণ করতে সাহায্য করে, যদি সেগুলি আর এবং এফ [এক্স]-এ বিদ্যমান থাকে। বিশেষ করে, যদি জিসিডি আর-এ বিদ্যমান থাকে, এবং যদি এক্স-কে একটি চলক-এ হ্রাস করা হয়, তবে এটি প্রমাণ করে যে জিসিডি আর [এক্স]-এ বিদ্যমান (ইউক্লিডের অ্যালগরিদম এফ [এক্স]-এ জিসিডি-র অস্তিত্ব প্রমাণ করে)। n চলকের একটি বহুপদীকে (n−1) চলকের বহুপদী বলয়ের উপর একটি অভিন্ন বহুপদী হিসাবে বিবেচনা করা যেতে পারে। সুতরাং চলকের সংখ্যার উপর একটি পুনরাবৃত্তি দেখায় যে যদি জিসিডি বিদ্যমান থাকে এবং আর-এ গণনা করা যেতে পারে, তবে সেগুলি বিদ্যমান এবং আর-এর উপর প্রতিটি বহু-বৈকল্পিক বহুপদী বলয়ে গণনা করা যেতে পারে। বিশেষত, যদি আর পূর্ণসংখ্যার বলয় বা একটি ক্ষেত্র হয়, তবে জিসিডিগুলি আর [x1,., xn]-এ বিদ্যমান এবং যা পূর্ববর্তী তা তাদের গণনা করার জন্য একটি অ্যালগরিদম সরবরাহ করে। একটি অনন্য ফ্যাক্টরাইজেশন ডোমেনের উপর একটি বহুপদী বলয় যে একটি অনন্য ফ্যাক্টরাইজেশন ডোমেন, তার প্রমাণও একই রকম, তবে এটি কোনও অ্যালগরিদম সরবরাহ করে না, কারণ একটি ক্ষেত্রের উপর অভিন্ন বহুপদীগুলিকে ফ্যাক্টর করার জন্য কোনও সাধারণ অ্যালগরিদম নেই (এমন ক্ষেত্রের উদাহরণ রয়েছে যার জন্য অভিন্ন বহুপদীগুলির জন্য কোনও ফ্যাক্টরাইজেশন অ্যালগরিদম বিদ্যমান নেই)। ছদ্ম-অবশিষ্ট ক্রম এই বিভাগে, আমরা একটি অবিচ্ছেদ্য ডোমেন Z (সাধারণত পূর্ণসংখ্যার রিং Z) এবং এর ভগ্নাংশের ক্ষেত্র Q (সাধারণত মূলদ সংখ্যার ক্ষেত্র Q) বিবেচনা করি। অভিন্ন বহুপদী বলয় Z [X]-এ দুটি বহুপদী A এবং B দেওয়া হলে, B দ্বারা A-এর ইউক্লিডীয় বিভাজন (Q-এর উপর) একটি ভাগফল এবং একটি অবশিষ্টাংশ প্রদান করে যা Z [X]-এর অন্তর্গত নাও হতে পারে। কারণ, যদি কেউ নিম্নলিখিত পলিনোমিয়ালগুলিতে ইউক্লিডের অ্যালগরিদম প্রয়োগ করে এবং ইউক্লিডের অ্যালগরিদমের ধারাবাহিক অবশিষ্টাংশগুলি হল একটি যে, ইনপুট পলিনোমিয়ালগুলির কোএফিসিয়েন্টগুলির ছোট ডিগ্রি এবং ছোট আকার সত্ত্বেও, একজনকে বরং বড় আকারের পূর্ণসংখ্যার ভগ্নাংশগুলিকে পরিচালনা এবং সহজ করতে হবে। ইউক্লিডের অ্যালগরিদমের একটি বৈকল্পিকের অনুমতি দেওয়ার জন্য ছদ্ম-বিভাগ চালু করা হয়েছে যার জন্য সমস্ত অবশিষ্টাংশ Z [X] এর অন্তর্গত। যদি এবং এবং a, b দ্বারা A এর ছদ্ম-বিভাগের ছদ্ম-অবশিষ্টাংশ, যা প্রিম (A, B) দ্বারা চিহ্নিত করা হয়, যেখানে B এর শীর্ষস্থানীয় সহগ (Xb এর সহগ)। Z [X]-এ দুটি বহুপদীর ছদ্ম-বিভাগের ছদ্ম-অবশিষ্টাংশ সর্বদা Z [X]-এর অন্তর্গত। একটি ছদ্ম-অবশিষ্টাংশ ক্রম হল ইউক্লিডের অ্যালগরিদমের নির্দেশ প্রতিস্থাপনের মাধ্যমে প্রাপ্ত (ছদ্ম) অবশিষ্টাংশের ক্রম যেখানে α হল Z-এর একটি উপাদান যা সংখ্যার ঠিক প্রতিটি সহগকে বিভক্ত করে। α-এর বিভিন্ন পছন্দগুলি বিভিন্ন ছদ্ম-অবশিষ্ট ক্রম দেয়, যা পরবর্তী উপবিভাগগুলিতে বর্ণনা করা হয়েছে। যেহেতু দুটি বহুপদীর সাধারণ বিভাজক পরিবর্তিত হয় না যদি বহুপদগুলি বিপরীতমুখী ধ্রুবক (Q-তে) দ্বারা গুণ করা হয়, একটি ছদ্ম-অবশিষ্ট ক্রমের শেষ অ-শূন্য পদটি হল ইনপুট বহুপদের একটি GCD (Q [X]-এ)। অতএব, সিউডো-রিমেন্ডার সিকোয়েন্সগুলি কিউ-তে ভগ্নাংশ প্রবর্তন না করে কিউ [এক্স]-এ জিসিডি গণনা করার অনুমতি দেয়। কিছু প্রসঙ্গে, ছদ্ম-অবশিষ্টাংশের নেতৃস্থানীয় সহগের চিহ্ন নিয়ন্ত্রণ করা অপরিহার্য। এটি সাধারণত ফলাফল এবং উপ-ফলাফল গণনা করার সময় বা স্টর্মের উপপাদ্য ব্যবহার করার ক্ষেত্রে হয়। এই নিয়ন্ত্রণ হয় ছদ্ম-অবশিষ্টাংশের সংজ্ঞায় এর পরম মান দ্বারা প্রতিস্থাপিত করে বা এর চিহ্ন নিয়ন্ত্রণ করে করা যেতে পারে (যদি অবশিষ্টাংশের সমস্ত সহগকে ভাগ করা হয়, তবে একই কথা প্রযোজ্য)। ট্রিভিয়াল সিউডো-রিমেন্ডার সিকোয়েন্স সবচেয়ে সহজ (সংজ্ঞায়িত করার জন্য) অবশিষ্টাংশ সিকোয়েন্স সর্বদা গ্রহণ করে। বাস্তবে, এটি আকর্ষণীয় নয়, কারণ সহগের আকার ইনপুট পলিনোমিয়ালের মাত্রার সাথে তাত্পর্যপূর্ণভাবে বৃদ্ধি পায়। এটি পূর্ববর্তী বিভাগের উদাহরণে স্পষ্টভাবে প্রদর্শিত হয়, যার জন্য ধারাবাহিক ছদ্ম-অবশিষ্টাংশগুলি হল অ্যালগরিদমের প্রতিটি পুনরাবৃত্তিতে ধারাবাহিক অবশিষ্টাংশের সহগের সংখ্যার সংখ্যা দ্বিগুণেরও বেশি হয়। এটি তুচ্ছ ছদ্ম-অবশিষ্ট ক্রমগুলির সাধারণ আচরণ। প্রিমিটিভ সিউডো-রিমেন্ডার সিকোয়েন্স আদিম সিউডো-রিমেন্ডার সিকোয়েন্সটি α-এর জন্য সংখ্যার বিষয়বস্তু নিয়ে গঠিত। সুতরাং সমস্ত রি হল আদিম বহুপদী। আদিম ছদ্ম-অবশিষ্টাংশ ক্রম হল ছদ্ম-অবশিষ্টাংশ ক্রম, যা ক্ষুদ্রতম সহগ তৈরি করে। তবে এটির জন্য জেড-এ বেশ কয়েকটি জিসিডি গণনা করা প্রয়োজন, এবং তাই অনুশীলনে ব্যবহার করার জন্য যথেষ্ট দক্ষ নয়, বিশেষত যখন জেড নিজেই একটি বহুপদী বলয়। পূর্ববর্তী বিভাগগুলির মতো একই ইনপুট সহ, ক্রমবর্ধমান অবশিষ্টাংশগুলি, তাদের বিষয়বস্তু দ্বারা বিভাজনের পরে হয় সহগগুলির ছোট আকার এই সত্যটি লুকিয়ে রাখে যে বেশ কয়েকটি পূর্ণসংখ্যা জিসিডি এবং জিসিডি দ্বারা বিভাগ গণনা করা হয়েছে। একটি উপ-ফলাফল ক্রম ছদ্ম-অবশিষ্টাংশ দিয়েও গণনা করা যেতে পারে। প্রক্রিয়াটি এমনভাবে α নির্বাচন করে যাতে প্রতিটি r একটি উপ-ফলস্বরূপ বহুপদী হয়। আশ্চর্যজনকভাবে, α-এর গণনা খুব সহজ (নীচে দেখুন)। অন্যদিকে, অ্যালগরিদমের সঠিকতার প্রমাণ কঠিন, কারণ এটি পরপর দুটি অবশিষ্টাংশের ডিগ্রির পার্থক্যের সমস্ত সম্ভাবনা বিবেচনা করা উচিত। উপ-ফলস্বরূপ ক্রমের সহগগুলি আদিম ছদ্ম-অবশিষ্ট ক্রমের তুলনায় খুব কমই বড় হয়। যেহেতু Z-এ GCD গণনার প্রয়োজন হয় না, তাই ছদ্ম-অবশিষ্টাংশ সহ উপ-ফলাফল ক্রমটি সবচেয়ে কার্যকর গণনা দেয়। পূর্ববর্তী বিভাগগুলির মতো একই ইনপুট সহ, ধারাবাহিক অবশিষ্টাংশগুলি হল সহগগুলির একটি যুক্তিসঙ্গত আকার রয়েছে। এগুলি কোনও জিসিডি গণনা ছাড়াই প্রাপ্ত হয়, শুধুমাত্র সঠিক বিভাগ। এটি এই অ্যালগরিদমটিকে আদিম সিউডো-রিমেন্ডার সিকোয়েন্সের তুলনায় আরও দক্ষ করে তোলে। ছদ্ম-অবশিষ্টাংশের সাথে উপ-ফলাফলের ক্রম গণনা করার অ্যালগরিদমটি নীচে দেওয়া হল। এই অ্যালগরিদমে, ইনপুট হল Z [X]-এ বহুপদের একটি জোড়া। এগুলি হল Z [X]-এর ধারাবাহিক ছদ্ম অবশিষ্টাংশ, চলকগুলি হল i এবং অ-ঋণাত্মক পূর্ণসংখ্যা, এবং গ্রীক অক্ষরগুলি Z-এর উপাদানগুলিকে নির্দেশ করে। ডিগ () এবং রেম () ফাংশনগুলি একটি বহুপদীর মাত্রা এবং ইউক্লিডীয় বিভাগের অবশিষ্টাংশকে নির্দেশ করে। অ্যালগরিদমে, এই অবশিষ্টাংশ সবসময় Z [X]-এ থাকে। পরিশেষে চিহ্নিত/নির্দেশিত বিভাগগুলি সর্বদা সঠিক হয় এবং তাদের ফলাফল হয় Z [X] অথবা Z-এ থাকে। দ্রষ্টব্যঃ "এলসি" মানে হল নেতৃস্থানীয় সহগ, যা চলকের সর্বোচ্চ মাত্রার সহগ। এই অ্যালগরিদম শুধুমাত্র সর্বশ্রেষ্ঠ সাধারণ বিভাজক (শেষ অ-শূন্য) গণনা করে না, তবে সমস্ত উপ-ফলাফল বহুপদীও গণনা করেঃ অবশিষ্টাংশ হল-তম উপ-ফলাফল বহুপদী। যদি,-তম উপ-ফলস্বরূপ বহুপদী হয়। অন্যান্য সমস্ত উপ-ফলস্বরূপ বহুপদ শূন্য। সিউডো-রিমেন্ডার সহ স্টর্ম সিকোয়েন্স স্টর্ম সিকোয়েন্সের মতো একই বৈশিষ্ট্যযুক্ত সিকোয়েন্স নির্মাণের জন্য সিউডো-রিমেন্ডার ব্যবহার করা যেতে পারে। এর জন্য ধারাবাহিক ছদ্ম-অবশিষ্টাংশের লক্ষণগুলি নিয়ন্ত্রণ করা প্রয়োজন, যাতে স্টর্ম ক্রমের মতো একই চিহ্ন থাকে। একটি পরিবর্তিত ছদ্ম-অবশিষ্টাংশকে নিম্নরূপ সংজ্ঞায়িত করে এটি করা যেতে পারে। যদি এবং এবং a, b দ্বারা A-এর ছদ্ম-বিভাগের পরিবর্তিত ছদ্ম-অবশিষ্ট প্রিম2 (A, B) হয় যেখানে |lc (B)। হল B-এর শীর্ষস্থানীয় সহগের পরম মান (Xb-এর সহগ)। পূর্ণসংখ্যা সহগ সহ ইনপুট পলিনোমিয়ালগুলির জন্য, এটি পূর্ণসংখ্যা সহগ সহ পলিনোমিয়ালগুলির সমন্বয়ে গঠিত স্টর্ম সিকোয়েন্সগুলির পুনরুদ্ধারের অনুমতি দেয়। সাব-রেসালট্যান্ট সিউডো-রিমেন্ডার সিকোয়েন্স একইভাবে পরিবর্তিত হতে পারে, এই ক্ষেত্রে অবশিষ্টাংশের চিহ্নগুলি যুক্তিসঙ্গতগুলির উপর গণনা করা চিহ্নগুলির সাথে মিলে যায়। লক্ষ্য করুন যে উপরে প্রদত্ত সাব-রেজাল্ট্যান্ট সিউডো-রিমেন্ডার সিকোয়েন্স গণনা করার জন্য অ্যালগরিদমটি ভুল সাব-রেসাল্ট্যান্ট পলিনোমিয়াল গণনা করবে যদি কেউ এর পরিবর্তে ব্যবহার করে। মডুলার জি. সি. ডি অ্যালগরিদম যদি এফ এবং জি কিছু সীমাবদ্ধভাবে উত্পন্ন ক্ষেত্র এফ-এর জন্য এফ [এক্স]-এ বহুপদী হয়, তবে ইউক্লিডীয় অ্যালগরিদম তাদের জি. সি. ডি গণনা করার সবচেয়ে প্রাকৃতিক উপায়। যাইহোক, আধুনিক কম্পিউটার বীজগণিত সিস্টেমগুলি কেবল তখনই এটি ব্যবহার করে যখন মধ্যবর্তী অভিব্যক্তি স্ফীত নামক একটি ঘটনার কারণে F সীমাবদ্ধ হয়। যদিও ইউক্লিডীয় অ্যালগরিদমের সময় ডিগ্রি হ্রাস পেতে থাকে, যদি এফ সীমাবদ্ধ না হয় তবে গণনার সময় বহুপদীগুলির বিট আকার (কখনও কখনও নাটকীয়ভাবে) বৃদ্ধি পেতে পারে কারণ এফ-এ পুনরাবৃত্ত গাণিতিক ক্রিয়াকলাপগুলি বৃহত্তর অভিব্যক্তির দিকে পরিচালিত করে। উদাহরণস্বরূপ, দুটি মূলদ সংখ্যার যোগ যার হরগুলি b দ্বারা আবদ্ধ, একটি মূলদ সংখ্যার দিকে পরিচালিত করে যার হরটি b2 দ্বারা আবদ্ধ, তাই সবচেয়ে খারাপ ক্ষেত্রে, বিটের আকার মাত্র একটি ক্রিয়াকলাপে প্রায় দ্বিগুণ হতে পারে। গণনা ত্বরান্বিত করতে, একটি রিং D নিন যার জন্য f এবং g D [x] এ রয়েছে এবং একটি আদর্শ I নিন যাতে D/I একটি সসীম রিং হয়। তারপর ইউক্লিডীয় অ্যালগরিদম দিয়ে এই সীমাবদ্ধ বলয়ের উপর জিসিডি গণনা করুন। পুনর্গঠন কৌশল ব্যবহার করা (চীনা অবশিষ্ট উপপাদ্য, যুক্তিসঙ্গত পুনর্গঠন ইত্যাদি) কেউ তার ইমেজ মডুলো থেকে f এবং g এর GCD পুনরুদ্ধার করতে পারে বেশ কয়েকটি আদর্শ I। কেউ প্রমাণ করতে পারে যে এটি কাজ করে যদি কেউ অ-ন্যূনতম ডিগ্রি সহ মডুলার চিত্রগুলি ত্যাগ করে এবং আদর্শ I মডুলো এড়িয়ে চলে যা একটি নেতৃস্থানীয় সহগ অদৃশ্য হয়ে যায়। ধরুন, এবং। যদি আমরা গ্রহণ করি তবে এটি একটি সসীম বলয় (কোনও ক্ষেত্র নয় কারণ এটি সর্বাধিক নয়)। ইউক্লিডীয় অ্যালগরিদম ইন-এর চিত্রগুলিতে প্রয়োগ করা হয় এবং 1 রিটার্ন করে। এর মানে হল যে ইন-এর জিসিডি অবশ্যই 1 হতে হবে। লক্ষ্য করুন যে এই উদাহরণটি সহজেই যে কোনও পদ্ধতিতে পরিচালনা করা যেতে পারে কারণ অভিব্যক্তি স্ফীত হওয়ার জন্য ডিগ্রিগুলি খুব ছোট ছিল, তবে এটি চিত্রিত করে যে যদি দুটি বহুপদীর জিসিডি 1 থাকে তবে মডুলার অ্যালগরিদমটি একটি একক আদর্শের পরে শেষ হওয়ার সম্ভাবনা রয়েছে। আরও দেখুন বহুপদী বিষয়ের তালিকা মাল্টিভ্যারিয়েট ডিভিশন অ্যালগরিদম রেফারেন্স পলিনোমিয়াল কম্পিউটার বীজগণিত