Polynomial greatest common divisor
الجبرا میں، دو کثیر الجہتی کا سب سے بڑا مشترکہ تقسیم کنندہ (اکثر جی سی ڈی کے طور پر مختصر کیا جاتا ہے) ایک کثیر الجہتی ہے، جو سب سے زیادہ ممکنہ ڈگری کا ہے، جو دونوں اصل کثیر الجہتی کا عنصر ہے۔ یہ تصور دو عددوں کے سب سے بڑے مشترکہ تقسیم کار کے مترادف ہے۔ کسی فیلڈ پر غیر متغیر کثیر الجہتی کے اہم معاملے میں کثیر الجہتی GCD کا حساب لگایا جا سکتا ہے، جیسے کہ عدد GCD کے لیے، طویل تقسیم کا استعمال کرتے ہوئے یوکلڈین الگورتھم کے ذریعے۔ کثیر الجہتی GCD کی تعریف صرف ایک الٹا مستقل کے ذریعہ ضرب تک کی جاتی ہے۔ انٹیجر جی سی ڈی اور کثیر الجہتی جی سی ڈی کے درمیان مماثلت ان تمام خصوصیات کو غیر متغیر کثیر الجہتی تک بڑھانے کی اجازت دیتی ہے جو یوکلڈین الگورتھم اور یوکلڈین ڈویژن سے اخذ کی جا سکتی ہیں۔ مزید برآں، کثیر الجہتی جی سی ڈی کی مخصوص خصوصیات ہیں جو اسے الجبرا کے مختلف شعبوں میں ایک بنیادی تصور بناتی ہیں۔ عام طور پر، دو کثیر الجہتی کے جی سی ڈی کی جڑیں دو کثیر الجہتی کی مشترکہ جڑیں ہیں، اور یہ ان کی گنتی کیے بغیر جڑوں کے بارے میں معلومات فراہم کرتا ہے۔ مثال کے طور پر، کثیر الجہتی کے متعدد جڑ کثیر الجہتی کے جی سی ڈی اور اس کے مشتق کی جڑیں ہیں، اور مزید جی سی ڈی کے حساب سے کثیر الجہتی کے مربع فری فیکٹرائزیشن کا حساب لگانے کی اجازت ملتی ہے، جو کثیر الجہتی فراہم کرتا ہے جس کی جڑیں اصل کثیر الجہتی کی دی گئی ضرب کی جڑیں ہیں۔ سب سے بڑے مشترکہ تقسیم کار کی وضاحت کی جا سکتی ہے اور زیادہ عام طور پر، کسی فیلڈ یا انٹیجرز کی رنگ پر ملٹی ویریٹ کثیر الجہتی کے لیے، اور ایک منفرد فیکٹرائزیشن ڈومین پر بھی موجود ہے۔ جیسے ہی کوفشنٹس کے دائرے میں جی سی ڈی الگورتھم ہوتا ہے، ان کا حساب لگانے کے لیے الگورتھم موجود ہوتے ہیں۔ یہ الگورتھم متغیرات کی تعداد پر تکرار کے ذریعے آگے بڑھتے ہیں تاکہ مسئلے کو یوکلڈین الگورتھم کے مختلف قسم تک کم کیا جا سکے۔ وہ کمپیوٹر الجبرا میں ایک بنیادی ٹول ہیں، کیونکہ کمپیوٹر الجبرا سسٹم ان کا استعمال فریکشن کو آسان بنانے کے لیے منظم طریقے سے کرتے ہیں۔ اس کے برعکس، کثیر الجہتی جی سی ڈی کا زیادہ تر جدید نظریہ کمپیوٹر الجبرا سسٹمز کی کارکردگی کی ضرورت کو پورا کرنے کے لیے تیار کیا گیا ہے۔ عام تعریف ایک انٹیگرل ڈومین میں کوفشنٹس کے ساتھ کثیر الجہتی ہونے دیں، عام طور پر ایک فیلڈ یا انٹیجرز۔ اور کا سب سے بڑا مشترکہ تقسیم کنندہ ایک کثیر الجہتی ہے جو اور کو تقسیم کرتا ہے، اور اس طرح کہ ہر مشترکہ تقسیم کنندہ کا بھی تقسیم کرتا ہے۔ کثیر الجہتی کے ہر جوڑے (دونوں صفر نہیں) میں جی سی ڈی ہوتا ہے اگر اور صرف اس صورت میں جب ایک منفرد فیکٹرائزیشن ڈومین ہو۔ اگر ایک فیلڈ ہے اور دونوں صفر نہیں ہیں، تو ایک کثیر الجہتی ایک سب سے بڑا مشترکہ تقسیم کنندہ ہے اگر اور صرف اس صورت میں جب یہ دونوں کو تقسیم کرتا ہے اور، اور اس خاصیت والے کثیر الجہتی میں اس کی سب سے بڑی ڈگری ہے۔ اگر، GCD 0 ہے۔ تاہم، کچھ مصنفین کا خیال ہے کہ اس معاملے میں اس کی وضاحت نہیں کی گئی ہے۔ اور کا سب سے بڑا مشترکہ تقسیم کنندہ عام طور پر ظاہر کیا جاتا ہے۔ " سب سے بڑا مشترکہ تقسیم کار منفرد نہیں ہے: اگر اور کا جی سی ڈی ہے، تو کثیر الجہتی ایک اور جی سی ڈی ہے اگر اور صرف اس صورت میں جب اس طرح کا کوئی الٹا عنصر موجود ہو اور۔ دوسرے لفظوں میں، GCD ایک الٹا مستقل کی طرف سے ضرب تک منفرد ہے۔ انٹیجرز کے معاملے میں، اس غیر تعین کو جی سی ڈی کے طور پر منتخب کرکے طے کیا گیا ہے، منفرد جو مثبت ہے (ایک اور ہے، جو اس کے برعکس ہے)۔ اس روایت کے ساتھ، دو عددوں کا GCD بھی سب سے بڑا (معمول کی ترتیب کے لیے) مشترکہ تقسیم کنندہ ہے۔ تاہم، چونکہ ایک انٹیگرل ڈومین پر کثیر الجہتی کے لیے کوئی قدرتی کل ترتیب نہیں ہے، اس لیے یہاں کوئی بھی اسی طرح آگے نہیں بڑھ سکتا۔ کسی فیلڈ پر غیر متغیر کثیر الجہتی کے لیے، کسی کو اضافی طور پر جی سی ڈی کو مونیک ہونے کی ضرورت پڑ سکتی ہے (یعنی اس کے سب سے زیادہ ڈگری کے گتانک کے طور پر 1 ہونا)، لیکن زیادہ عام معاملات میں کوئی عمومی روایت نہیں ہے۔ لہذا، مساوات جیسے یا اشارے کی عام خلاف ورزیاں ہیں جن کو پڑھا جانا چاہیے "یہ" اور "اور" کا جی سی ڈی ہے اور جن میں جی سی ڈی کا ایک ہی سیٹ اور ہے "۔ خاص طور پر، اس کا مطلب یہ ہے کہ الٹا مستقل واحد مشترکہ تقسیم کار ہیں۔ اس معاملے میں، انٹیجر کیس کے ساتھ مشابہت سے، ایک کہتا ہے کہ اور ہیں۔ جیسا کہ اوپر بیان کیا گیا ہے، دو کثیر الجہتی کا GCD موجود ہے اگر کوفیشنٹس کا تعلق یا تو کسی فیلڈ، انٹیجرز کی رنگ، یا زیادہ عام طور پر کسی منفرد فیکٹرائزیشن ڈومین سے ہو۔ اگر اور کا کوئی مشترکہ تقسیم کنندہ ہے، تو ان کے جی سی ڈی کو تقسیم کرتا ہے۔ کسی بھی کثیر الجہتی کے لیے۔ یہ خاصیت یوکلڈین الگورتھم کے ثبوت کی بنیاد پر ہے۔ کوفشنٹس کی رنگ کے کسی بھی الٹا عنصر کے لیے،۔ لہذا کسی بھی اسکیلر کے لیے جو الٹا ہو۔ اگر، تب۔ اگر، تب۔ دو غیر متغیر کثیر الجہتی کے لیے اور ایک فیلڈ پر، کثیر الجہتی موجود ہیں اور، اس طرح کہ اور (بیزوٹ کی شناخت) کے اس طرح کے ہر لکیری امتزاج کو تقسیم کرتا ہے۔ تین یا زیادہ کثیر الجہتی کے سب سے بڑے مشترکہ تقسیم کار کی تعریف اسی طرح کی جا سکتی ہے جیسے دو کثیر الجہتی کے لیے ہوتی ہے۔ اسے شناخت کے لحاظ سے دو کثیر الجہتی کے جی سی ڈی سے بار بار شمار کیا جا سکتا ہے: اور ہاتھ کے حساب سے جی سی ڈی دو کثیر الجہتی کے سب سے بڑے مشترکہ تقسیم کار کو تلاش کرنے کے کئی طریقے ہیں۔ ان میں سے دو ہیں: کثیر الجہتی کی فیکٹرائزیشن، جس میں ہر ایک اظہار کے عوامل کو تلاش کیا جاتا ہے، پھر عوامل کے ہر سیٹ کے اندر سے سب کے پاس موجود مشترکہ عوامل کا مجموعہ منتخب کیا جاتا ہے۔ یہ طریقہ صرف سادہ صورتوں میں کارآمد ثابت ہو سکتا ہے، کیونکہ فیکٹرنگ عام طور پر سب سے بڑے مشترکہ تقسیم کار کی گنتی سے زیادہ مشکل ہوتی ہے۔ یوکلڈین الگورتھم، جسے دو کثیر الجہتی کے جی سی ڈی کو اسی انداز میں تلاش کرنے کے لیے استعمال کیا جا سکتا ہے جیسے دو اعداد کے لیے۔ فیکٹرنگ کا استعمال کرتے ہوئے دو کثیر الجہتی کے جی سی ڈی کو تلاش کرنے کے لیے، صرف دو کثیر الجہتی کو مکمل طور پر فیکٹر کریں۔ پھر، تمام عام عوامل کا پروڈکٹ لیں۔ اس مرحلے پر، ضروری نہیں کہ ہمارے پاس ایک مونیک کثیر الجہتی ہو، لہذا آخر میں اسے ایک مستقل سے ضرب دیں تاکہ اسے مونیک کثیر الجہتی بنایا جا سکے۔ یہ دو کثیر الجہتی کا جی سی ڈی ہوگا کیونکہ اس میں تمام مشترکہ تقسیم کار شامل ہیں اور یہ مونیک ہے۔ مثال ایک: اور کا جی سی ڈی تلاش کریں۔ اس طرح، ان کا جی سی ڈی ہے۔ یوکلڈین الگورتھم فیکٹرنگ کثیر الجہتی مشکل ہو سکتے ہیں، خاص طور پر اگر کثیر الجہتی کی ڈگری بڑی ہو۔ یوکلڈین الگورتھم ایک ایسا طریقہ ہے جو کثیر الجہتی کے کسی بھی جوڑے کے لیے کام کرتا ہے۔ یہ یوکلڈین تقسیم کا بار بار استعمال کرتا ہے۔ اس الگورتھم کو دو نمبروں پر استعمال کرتے وقت، ہر مرحلے پر نمبروں کا سائز کم ہو جاتا ہے۔ کثیر الجہتی کے ساتھ، ہر مرحلے پر کثیر الجہتی کی ڈگری کم ہو جاتی ہے۔ آخری غیر صفر بقیہ، جسے اگر ضروری ہو تو مونیک بنایا جاتا ہے، دو کثیر الجہتی کا GCD ہے۔ مزید خاص طور پر، دو کثیر الجہتی کے جی سی ڈی کو تلاش کرنے کے لیے اور، کوئی فرض کر سکتا ہے (بصورت دیگر، جی سی ڈی ہے)، اور یوکلڈین ڈویژن دو کثیر الجہتی فراہم کرتا ہے، حصص اور، بقیہ اس طرح کہ ایک کثیر الجہتی دونوں کو تقسیم کرتا ہے اور اگر اور صرف اس صورت میں جب یہ دونوں کو تقسیم کرتا ہے اور۔ اس طرح ترتیب دینے سے کوئی بھی نئے کثیر الجہتی وغیرہ حاصل کرنے کے لیے یوکلڈین ڈویژن کو دہرا سکتا ہے۔ ہر مرحلے پر ہمارے پاس ہے لہذا ترتیب بالآخر ایک ایسے مقام پر پہنچ جائے گی جس پر کسی کو جی سی ڈی مل گیا ہے: مثال: کا جی سی ڈی تلاش کرنا اور: چونکہ آخری غیر صفر بقیہ ہے، یہ اصل کثیر الجہتی کا جی سی ڈی ہے، اور مونیک جی سی ڈی ہے۔ اس مثال میں، دوسرے مرحلے سے پہلے 12 کو فیکٹر کرکے ڈینومینیٹرز کو متعارف کرانے سے بچنا مشکل نہیں ہے۔ یہ ہمیشہ سڈو ریمینڈر سیکوینسز کا استعمال کرکے کیا جا سکتا ہے، لیکن، بغیر کسی پرواہ کے، یہ کمپیوٹیشن کے دوران بہت بڑے انٹیجرز متعارف کرا سکتا ہے۔ لہذا، کمپیوٹر کمپیوٹیشن کے لیے، دیگر الگورتھم استعمال کیے جاتے ہیں، جو ذیل میں بیان کیے گئے ہیں۔ یہ طریقہ صرف اس صورت میں کام کرتا ہے جب کوئی کمپیوٹیشن کے دوران پائے جانے والے کوفشنٹس کی صفر سے مساوات کی جانچ کر سکے۔ لہذا، عملی طور پر، کوفشنٹس لازمی طور پر انٹیجرز، ریشنل نمبرز، ایک محدود فیلڈ کے عناصر ہونے چاہئیں، یا ان کا تعلق پچھلے فیلڈز میں سے کسی ایک کے کسی حتمی طور پر تیار کردہ فیلڈ ایکسٹینشن سے ہونا چاہیے۔ اگر کوفشنٹس فلوٹنگ پوائنٹ نمبرز ہیں جو حقیقی نمبروں کی نمائندگی کرتے ہیں جو صرف تقریبا معلوم ہوتے ہیں، تو کسی کو اچھی طرح سے متعین کمپیوٹیشن نتیجہ حاصل کرنے کے لیے جی سی ڈی کی ڈگری معلوم ہونی چاہیے (یہ عددی طور پر مستحکم نتیجہ ہے ؛ اس صورت میں دوسری تکنیکیں استعمال کی جا سکتی ہیں، جو عام طور پر واحد قدر کے سڑنے پر مبنی ہوتی ہیں۔ کسی فیلڈ میں کوفشنٹس کے ساتھ غیر متغیر کثیر الجہتی کسی فیلڈ پر غیر متغیر کثیر الجہتی کا معاملہ کئی وجوہات کی بناء پر خاص طور پر اہم ہے۔ سب سے پہلے، یہ سب سے ابتدائی معاملہ ہے اور اس لیے الجبرا کے زیادہ تر ابتدائی کورسز میں ظاہر ہوتا ہے۔ دوسرا، یہ انٹیجرز کے معاملے سے بہت ملتا جلتا ہے، اور یہ مشابہت یوکلڈین ڈومین کے تصور کا ماخذ ہے۔ تیسری وجہ یہ ہے کہ ملٹی ویریٹ کیس اور ایک منفرد فیکٹرائزیشن ڈومین میں کوفیشنٹس کے لیے تھیوری اور الگورتھم اس خاص کیس پر مضبوطی سے مبنی ہیں۔ آخری لیکن کم از کم، کثیر الجہتی جی سی ڈی الگورتھم اور ماخوذ الگورتھم کسی کو کثیر الجہتی کی جڑوں کے بارے میں مفید معلومات حاصل کرنے کی اجازت دیتے ہیں، ان کی گنتی کیے بغیر۔ کثیر الجہتی کی یوکلڈین تقسیم، جو جی سی ڈیز کی گنتی کے لیے یوکلڈ کے الگورتھم میں استعمال ہوتی ہے، انٹیجرز کی یوکلڈین تقسیم سے بہت ملتی جلتی ہے۔ اس کا وجود مندرجہ ذیل نظریہ پر مبنی ہے: ایک فیلڈ پر بیان کردہ دو غیر متغیر کثیر الجہتی a اور b ष्णد 0 کو دیکھتے ہوئے، دو کثیر الجہتی q (حصص) اور r (بقیہ) موجود ہیں جو مطمئن کرتے ہیں اور جہاں "ڈگری (.)" ڈگری کو ظاہر کرتا ہے اور صفر کثیر الجہتی کی ڈگری کو منفی ہونے کے طور پر بیان کیا جاتا ہے۔ مزید برآں، q اور r کو ان رلیشنز کے ذریعے منفرد طور پر بیان کیا جاتا ہے۔ انٹیجرز کی یوکلیڈین تقسیم سے فرق یہ ہے کہ، انٹیجرز کے لیے، ڈگری کو مطلق قدر سے تبدیل کیا جاتا ہے، اور یہ کہ انفرادیت حاصل کرنے کے لیے کسی کو یہ سمجھنا پڑتا ہے کہ r غیر منفی ہے۔ وہ حلقے جن کے لیے اس طرح کا نظریہ موجود ہے، یوکلڈین ڈومینز کہلاتے ہیں۔ انٹیجرز کی طرح، کثیر الجہتی کی یوکلڈین تقسیم کا حساب لانگ ڈویژن الگورتھم کے ذریعے کیا جا سکتا ہے۔ یہ الگورتھم عام طور پر کاغذ اور پنسل کے حساب کے لیے پیش کیا جاتا ہے، لیکن یہ کمپیوٹر پر اچھی طرح سے کام کرتا ہے جب اسے مندرجہ ذیل طور پر رسمی بنایا جاتا ہے (نوٹ کریں کہ متغیرات کے نام طویل تقسیم کے پنسل اور کاغذ کے حساب میں کاغذ کی شیٹ کے علاقوں سے بالکل مطابقت رکھتے ہیں)۔ مندرجہ ذیل حساب میں "ڈیگ" کا مطلب اس کی دلیل کی ڈگری (کنونشن کے ساتھ) ہے، اور "ایل سی" کا مطلب معروف گتانک ہے، جو متغیر کی اعلی ترین ڈگری کا گتانک ہے۔ اس الگورتھم کی صداقت کا ثبوت اس حقیقت پر منحصر ہے کہ پورے "وائل" لوپ کے دوران، ہمارے پاس ایک غیر منفی عدد ہے جو ہر تکرار پر کم ہوتا ہے۔ اس طرح اس الگورتھم کی صداقت کا ثبوت بھی یوکلڈین تقسیم کی صداقت کو ثابت کرتا ہے۔ یوکلڈ کا الگورتھم جہاں تک انٹیجرز کا تعلق ہے، یوکلڈین ڈویژن ہمیں جی سی ڈیز کی کمپیوٹنگ کے لیے یوکلڈ کے الگورتھم کی وضاحت کرنے کی اجازت دیتا ہے۔ دو کثیر الجہتی a اور b سے شروع کرتے ہوئے، یوکلڈ کا الگورتھم b = 0 تک جوڑے کو بار بار تبدیل کرنے پر مشتمل ہوتا ہے (جہاں "" یوکلڈین ڈویژن کے بقیہ حصے کی نشاندہی کرتا ہے، جو پچھلے حصے کے الگورتھم کے ذریعہ شمار کیا جاتا ہے)۔ جی سی ڈی آخری غیر صفر بقیہ ہے۔ یوکلڈ کے الگورتھم کو ریکرسو پروگرامنگ سٹائل میں باضابطہ بنایا جا سکتا ہے: لازمی پروگرامنگ سٹائل میں، وہی الگورتھم بن جاتا ہے، جو ہر انٹرمیڈیٹ بقیہ کو ایک نام دیتا ہے: ڈگری کی ترتیب سختی سے کم ہو رہی ہے۔ اس طرح، زیادہ سے زیادہ، اقدامات کے بعد، ایک کالعدم ریمینڈر ملتا ہے۔ جیسا کہ ایک ہی تقسیم کنندگان ہوتے ہیں، مشترکہ تقسیم کنندگان کا سیٹ یوکلڈ کے الگورتھم کے ذریعہ تبدیل نہیں ہوتا ہے اور اس طرح تمام جوڑوں میں مشترکہ تقسیم کنندگان کا ایک ہی سیٹ ہوتا ہے۔ اور کے مشترکہ تقسیم کار اس طرح اور 0 کے مشترکہ تقسیم کار ہیں۔ اس طرح اور کا جی سی ڈی ہے۔ یہ نہ صرف یہ ثابت کرتا ہے کہ یوکلڈ کا الگورتھم جی سی ڈیز کا حساب لگاتا ہے بلکہ یہ بھی ثابت کرتا ہے کہ جی سی ڈیز موجود ہیں۔ بیزاوٹ کی شناخت اور توسیعی جی سی ڈی الگورتھم بیزاوٹ کی شناخت ایک جی سی ڈی سے متعلق نظریہ ہے، جو ابتدائی طور پر انٹیجرز کے لیے ثابت ہوتا ہے، جو ہر پرنسپل آئیڈیل ڈومین کے لیے درست ہے۔ کسی فیلڈ پر غیر متغیر کثیر الجہتی کے معاملے میں، اسے مندرجہ ذیل طور پر بیان کیا جا سکتا ہے۔ کثیر الجہتی کے معاملے میں اس نتیجے کی دلچسپی یہ ہے کہ کثیر الجہتی کا حساب لگانے کے لیے ایک موثر الگورتھم موجود ہے اور یہ الگورتھم لوپ کے ہر تکرار پر کیے گئے چند مزید حسابات کے ذریعے یوکلڈ کے الگورتھم سے مختلف ہے۔ اس لیے اسے توسیعی جی سی ڈی الگورتھم کہا جاتا ہے۔ یوکلڈ کے الگورتھم کے ساتھ ایک اور فرق یہ ہے کہ یہ صرف بقیہ کے بجائے یوکلڈین ڈویژن کے حصص، جسے "کوو" کہا جاتا ہے، کا بھی استعمال کرتا ہے۔ یہ الگورتھم مندرجہ ذیل طریقے سے کام کرتا ہے۔ اس بات کا ثبوت کہ الگورتھم اپنی آؤٹ پٹ تفصیلات کو مطمئن کرتا ہے اس حقیقت پر انحصار کرتا ہے کہ، ہر ایک کے لیے ہمارے پاس مؤخر الذکر مساوات ہے جس کا مطلب ہے ڈگریوں پر دعوی اس حقیقت سے ہوتا ہے کہ، ہر تکرار پر، ڈگری کی کمی کے ساتھ زیادہ سے زیادہ ڈگری اور اضافہ ہوتا ہے۔ اس الگورتھم کی ایک دلچسپ خصوصیت یہ ہے کہ، جب بیزاوٹ کی شناخت کے کوفیشنٹس کی ضرورت ہوتی ہے، تو ان کے جی سی ڈی کے ذریعہ ان پٹ کثیر الجہتی کا حصص مفت میں مل جاتا ہے۔ الجبرائی توسیعات کا ریاضی توسیعی جی سی ڈی الگورتھم کا ایک اہم اطلاق یہ ہے کہ یہ الجبرائی فیلڈ توسیعات میں تقسیم کا حساب لگانے کی اجازت دیتا ہے۔ کسی فیلڈ کی الجبرائی توسیع کو ایسے عنصر سے پیدا ہونے دیں جس کے کم سے کم کثیر الجہتی کی ڈگری ہو۔ کے عناصر کی نمائندگی عام طور پر اس سے کم ڈگری پر غیر متغیر کثیر الجہتی کے ذریعہ کی جاتی ہے۔ میں اضافہ محض کثیر الجہتی کا اضافہ ہے: میں ضرب کثیر الجہتی کا ضرب ہے جس کے بعد تقسیم ہوتا ہے: کے غیر صفر عنصر کا الٹا بیزوٹ کی شناخت میں گتانک ہے، جس کا حساب توسیعی جی سی ڈی الگورتھم کے ذریعے کیا جاسکتا ہے۔ (جی سی ڈی 1 ہے کیونکہ کم از کم کثیر الجہتی ناقابل تلافی ہے)۔ توسیعی جی سی ڈی الگورتھم کی تفصیلات میں ڈگریوں کی عدم مساوات سے پتہ چلتا ہے کہ ڈیگ () <ڈگری () حاصل کرنے کے لیے مزید تقسیم کی ضرورت نہیں ہے۔ ذیلی نتائج غیر متغیر کثیر الجہتی کے معاملے میں، سب سے بڑے مشترکہ تقسیم کاروں اور نتائج کے درمیان ایک مضبوط تعلق ہوتا ہے۔ مزید واضح طور پر، دو کثیر الجہتی P، Q کا نتیجہ P اور Q کے گتانک کا ایک کثیر الجہتی فعل ہے جس کی قیمت صفر ہے اگر اور صرف اس صورت میں جب P اور Q کا GCD مستقل نہ ہو۔ ذیلی نتیجہ کا نظریہ اس خاصیت کی عمومی شکل ہے جو عام طور پر دو کثیر الجہتی کے جی سی ڈی کی خصوصیت کی اجازت دیتا ہے، اور نتیجہ 0-th ذیلی نتیجہ کثیر الجہتی ہے۔ دو کثیر الجہتی P اور Q کا i-th ذیلی نتیجہ کثیر الجہتی Si (P، Q) زیادہ سے زیادہ i ڈگری کا ایک کثیر الجہتی ہے جس کے گتانک P اور Q کے گتانک کے کثیر الجہتی افعال ہیں، اور i-th پرنسپل ذیلی نتیجہ گتانک si (P، Q) Si (P، Q) کی ڈگری i کا گتانک ہے۔ ان کے پاس یہ خاصیت ہے کہ P اور Q کے GCD میں ڈگری d ہے اگر اور صرف اگر۔ اس صورت میں، ایس ڈی (پی، کیو) پی اور کیو کا جی سی ڈی ہے اور ذیلی نتیجہ خیز کثیر الجہتی کے ہر گتانک کو پی اور کیو کے سلویسٹر میٹرکس کے ذیلی میٹرکس کے تعین کنندہ کے طور پر بیان کیا جاتا ہے۔ اس کا مطلب یہ ہے کہ ذیلی نتائج اچھی طرح سے "مہارت" رکھتے ہیں۔ مزید واضح طور پر، ذیلی نتائج کو کسی بھی مواصلاتی رنگ R پر کثیر الجہتی کے لیے بیان کیا جاتا ہے، اور ان میں درج ذیل خاصیت ہوتی ہے۔ فرض کریں کہ φ، R کا ایک رنگ ہومومورفزم ہے جو ایک اور مواصلاتی رنگ S میں تبدیل ہوتا ہے۔ یہ ایک اور ہومومورفزم تک پھیلا ہوا ہے، جسے R اور S پر کثیر الجہتی بجتوں کے درمیان بھی ظاہر کیا جاتا ہے۔ پھر، اگر P اور Q R میں گتانک کے ساتھ غیر متغیر کثیر الجہتی ہیں اور پھر ذیلی نتیجہ والے کثیر الجہتی اور φ (P) اور φ (Q) کے پرنسپل ذیلی نتیجہ والے گتانک P اور Q کی شبیہہ φ ہیں۔ ذیلی نتائج میں دو اہم خصوصیات ہوتی ہیں جو انہیں انٹیجر کوفشنٹس کے ساتھ دو کثیر الجہتی کے جی سی ڈی کے کمپیوٹرز پر حساب کتاب کے لیے بنیادی بناتی ہیں۔ سب سے پہلے، تعین کاروں کے ذریعے ان کی تعریف حد بندی کی اجازت دیتی ہے، ہڈمارڈ عدم مساوات کے ذریعے، جی سی ڈی کے کوفیشنٹس کا سائز۔ دوم، یہ باؤنڈ اور اچھی تخصص کی خاصیت ماڈیولر کمپیوٹیشن اور چینی ریمائنڈر تھیوریم (نیچے دیکھیں) کے ذریعے انٹیجر کوفیشنٹس کے ساتھ دو کثیر الجہتی کے جی سی ڈی کا حساب لگانے کی اجازت دیتی ہے۔ تکنیکی تعریف آئیے ایک فیلڈ K میں کوفشنٹس کے ساتھ دو غیر متغیر کثیر الجہتی ہوں۔ آئیے ہم i سے کم ڈگری کے کثیر الجہتی کے طول و عرض i کے K ویکٹر اسپیس سے ظاہر کرتے ہیں۔ غیر منفی عدد i کے لیے اس طرح کہ i ≤ m اور i ≤ n، لکیری نقشہ اس طرح ہونے دیں کہ P اور Q کا نتیجہ سلویسٹر میٹرکس کا تعین کنندہ ہو، جو X کی طاقتوں کی بنیاد پر (مربع) میٹرکس ہے۔ آئیے ان میٹرکس کو مزید واضح طور پر بیان کریں۔ آئی <0 یا آئی> ایم کے لیے پائی = 0، اور آئی <0 یا آئی> این کے لیے کیو آئی = 0۔ سلویسٹر میٹرکس (ایم + این) × (ایم + این)-میٹرکس اس طرح ہے کہ آئی-ویں صف اور جے-ویں کالم کا گتانک جے ≤ این کے لیے پی ایم + جے − آئی اور جے> این کے لیے کیو جے − آئی ہے: میٹرکس ٹی آئی ایس کا (ایم + این − آئی) × (ایم + این − 2 آئی)-ذیلی میٹرکس ہے جو ایس کے ذریعے حاصل کیا جاتا ہے۔ پرنسپل سب ریسلٹنٹ گتانک si، Ti کی 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-th ذیلی نتیجہ کثیر میٹرکس پروڈکٹ viTi کا تعین کنندہ ہے۔ اس کا ڈگری جے کا گتانک ٹائی کے مربع ذیلی میٹرکس کا تعین کنندہ ہے جو اس کی m + n−2i−1 پہلی قطاروں اور (m + n−i−j)-th صف پر مشتمل ہے۔ ثبوت کا خاکہ یہ واضح نہیں ہے کہ، جیسا کہ بیان کیا گیا ہے، ذیلی نتائج مطلوبہ خصوصیات رکھتے ہیں۔ اس کے باوجود، ثبوت کافی آسان ہے اگر لکیری الجبرا اور کثیر الجہتی کی خصوصیات کو ایک ساتھ رکھا جائے۔ جیسا کہ بیان کیا گیا ہے، میٹرکس Ti کے کالم کی تصویر سے تعلق رکھنے والے کچھ کثیر الجہتی کے کوفشنٹس کے ویکٹر ہیں۔ i-th سب ریسلٹنٹ کثیر الجہتی Si کی تعریف سے پتہ چلتا ہے کہ اس کے کوفیشنٹس کا ویکٹر ان کالم ویکٹروں کا ایک لکیری مجموعہ ہے، اور اس طرح یہ کہ Si کا تعلق i کی شبیہہ سے ہے۔ اگر GCD کی ڈگری i سے زیادہ ہے، تو بیزاوٹ کی شناخت سے پتہ چلتا ہے کہ i کی شبیہہ میں ہر غیر صفر کثیر الجہتی کی ڈگری i سے بڑی ہے۔ اس کا مطلب ہے کہ Si = 0۔ اگر، دوسری طرف، GCD کی ڈگری i ہے، تو بیزاوٹ کی شناخت ایک بار پھر یہ ثابت کرنے کی اجازت دیتی ہے کہ GCD کے ضرب جن کی ڈگری m + n−i سے کم ہے، کی تصویر میں ہیں۔ ان ضربوں کی ویکٹر جگہ کا طول و عرض m + n − 2i ہے اور اس میں جوڑی کے لحاظ سے مختلف ڈگریوں کے کثیر الجہتی کی بنیاد ہوتی ہے، جو i سے چھوٹی نہیں ہوتی ہے۔ اس کا مطلب یہ ہے کہ ٹی آئی کے کالم ایکلون فارم کی m + n − 2i پہلی قطاروں کا ذیلی میٹرکس شناختی میٹرکس ہے اور اس طرح یہ کہ سی 0 نہیں ہے۔ اس طرح سی کی تصویر میں ایک کثیر الجہتی ہے، جو جی سی ڈی کا ایک ضرب ہے اور اس کی ڈگری ایک جیسی ہے۔ اس طرح یہ ایک سب سے بڑا مشترکہ تقسیم کنندہ ہے۔ جی سی ڈی اور روٹ فائنڈنگ اسکوائر فری فیکٹرائزیشن زیادہ تر روٹ فائنڈنگ الگورتھم کثیر الجہتی کے ساتھ برا سلوک کرتے ہیں جن کی متعدد جڑیں ہوتی ہیں۔ اس لیے جڑ تلاش کرنے والے الگورتھم کو کال کرنے سے پہلے ان کا پتہ لگانا اور انہیں ہٹانا مفید ہے۔ جی سی ڈی کا حساب متعدد جڑوں کے وجود کا پتہ لگانے کی اجازت دیتا ہے، کیونکہ کثیر الجہتی کے متعدد جڑیں کثیر الجہتی کے جی سی ڈی اور اس کے مشتق کی جڑیں ہوتی ہیں۔ کثیر الجہتی کے جی سی ڈی اور اس کے مشتق کا حساب لگانے کے بعد، مزید جی سی ڈی حسابات کثیر الجہتی کی مکمل مربع فری فیکٹرائزیشن فراہم کرتے ہیں، جو کہ ایک فیکٹرائزیشن ہے جہاں، ہر i کے لیے، کثیر الجہتی فائی یا تو 1 ہے اگر f میں ضرب i کی کوئی جڑ نہیں ہے یا مربع فری کثیر الجہتی ہے (جو کہ متعدد جڑ کے بغیر کثیر الجہتی ہے) جس کی جڑیں بالکل f کے ضرب i کی جڑیں ہیں (یون کا الگورتھم دیکھیں)۔ اس طرح مربع فری فیکٹرائزیشن متعدد جڑوں والی کثیر الجہتی کی جڑ کی تلاش کو کم ڈگری کے کئی مربع فری کثیر الجہتی کی جڑ کی تلاش میں کم کر دیتی ہے۔ مربع فری فیکٹرائزیشن بھی زیادہ تر کثیر الجہتی فیکٹرائزیشن الگورتھم کا پہلا قدم ہے۔ اسٹورم سیکوینس حقیقی کوفشنٹس کے ساتھ کثیر الجہتی کی اسٹورم سیکوینس یوکلڈ کے الگورتھم کے مختلف قسم کے ذریعہ فراہم کردہ بقایا جات کی ترتیب ہے جو کثیر الجہتی اور اس کے مشتق پر لاگو ہوتی ہے۔ اسٹرم سیکوینس حاصل کرنے کے لیے، یوکلڈ کے الگورتھم کی ہدایات کو صرف اس طرح تبدیل کیا جاتا ہے کہ V (a) ترتیب میں اشاروں کی تبدیلیوں کی تعداد ہو، جب ایک نقطہ a پر اس کا اندازہ لگایا جاتا ہے۔ اسٹرم کا نظریہ اس بات پر زور دیتا ہے کہ V (a) − V (b) وقفہ [a, b] میں کثیر الجہتی کے حقیقی جڑوں کی تعداد ہے۔ اس طرح اسٹرم سیکوینس ایک مقررہ وقفے میں حقیقی جڑوں کی تعداد کا حساب لگانے کی اجازت دیتا ہے۔ وقفے کو ذیلی تقسیم کرکے جب تک کہ ہر ذیلی وقفہ زیادہ سے زیادہ ایک جڑ پر مشتمل نہ ہو، یہ ایک الگورتھم فراہم کرتا ہے جو من مانی چھوٹی لمبائی کے وقفوں میں حقیقی جڑوں کا پتہ لگاتا ہے۔ کسی رنگ اور اس کے فریکشن کے فیلڈ پر GCD اس حصے میں، ہم ایک منفرد فیکٹرائزیشن ڈومین R پر کثیر الجہتی پر غور کرتے ہیں، عام طور پر انٹیجرز کی رنگ، اور اس کے فریکشن F کے فیلڈ پر، عام طور پر عقلی نمبروں کا فیلڈ، اور ہم R [X] اور F [X] کو ان رنگوں پر متغیرات کے سیٹ میں کثیر الجہتی کے رنگوں کی نشاندہی کرتے ہیں۔ ابتدائی پارٹ-کنٹینٹ فیکٹرائزیشن کثیر الجہتی p ωR [X] کا مواد، جسے "کونٹ (p)" کہا جاتا ہے، اس کے کوفشنٹس کا GCD ہے۔ ایک کثیر الجہتی q ωF [X] لکھا جا سکتا ہے جہاں p ωR [X] اور c ωR: یہ q (مثال کے طور پر ان کے پروڈکٹ) اور p = cq کے کوفیشنٹس کے تمام ڈینومینیٹرز کے c a ملٹیپل کے لیے کافی ہے۔ q کے مواد کی تعریف اس طرح کی گئی ہے: دونوں صورتوں میں، مواد کو R کی اکائی سے ضرب تک بیان کیا جاتا ہے۔ R [X] یا F [X] میں کثیر الجہتی کے ابتدائی حصے کی تعریف اس طرح کی جاتی ہے۔ دونوں صورتوں میں، یہ R [X] میں ایک کثیر الجہتی ہے جو ابتدائی ہے، جس کا مطلب ہے کہ 1 اس کے گتانک کا GCD ہے۔ اس طرح R [X] یا F [X] میں ہر کثیر الجہتی کو فیکٹرائز کیا جا سکتا ہے اور یہ فیکٹرائزیشن مواد کو R کی اکائی سے اور ابتدائی حصے کو اس اکائی کے الٹا سے ضرب دینے تک منفرد ہے۔ گاؤس کے لیما سے یہ ظاہر ہوتا ہے کہ دو ابتدائی کثیر الجہتی کا پروڈکٹ قدیم ہے۔ اس کے بعد R اور F پر GCD کے درمیان تعلق پچھلے حصے کے تعلقات R [X] اور F [X] میں GCD کے درمیان ایک مضبوط تعلق کی نشاندہی کرتے ہیں۔ ابہام سے بچنے کے لیے، نوٹیشن "جی سی ڈی" کو درج ذیل میں، اس رنگ کے ذریعے انڈیکس کیا جائے گا جس میں جی سی ڈی کا حساب لگایا جاتا ہے۔ اگر q1 اور q2 کا تعلق F [X] سے ہے، تو اگر p1 اور p2 کا تعلق R [X] سے ہے، تو اور اس طرح کثیر الجہتی GCD کی گنتی بنیادی طور پر F [X] اور R [X] پر ایک ہی مسئلہ ہے۔ عقلی اعداد پر غیر متغیر کثیر الجہتی کے لیے، کوئی یہ سوچ سکتا ہے کہ یوکلڈ کا الگورتھم جی سی ڈی کی گنتی کے لیے ایک آسان طریقہ ہے۔ تاہم، اس میں انٹیجرز کے حصوں کی ایک بڑی تعداد کو آسان بنانا شامل ہے، اور اس کے نتیجے میں الگورتھم موثر نہیں ہے۔ اس وجہ سے، انٹیجرز پر صرف کثیر الجہتی کے ساتھ کام کرنے کے لیے یوکلڈ کے الگورتھم میں ترمیم کرنے کے لیے طریقے تیار کیے گئے ہیں۔ وہ یوکلڈین ڈویژن کی جگہ لینے پر مشتمل ہوتے ہیں، جو ایک نام نہاد چھدم تقسیم کے ذریعے حصوں کو متعارف کراتا ہے، اور یوکلڈ کے الگورتھم کی بقیہ ترتیب کو نام نہاد چھدم باقی ترتیب کے ذریعے تبدیل کرتا ہے (نیچے دیکھیں)۔ اس بات کا ثبوت کہ کثیر متغیر کثیر الجہتی کے لیے GCD موجود ہے پچھلے حصے میں ہم نے دیکھا ہے کہ R [X] میں کثیر الجہتی کے GCD کو R اور F [X] میں GCD سے نکالا جا سکتا ہے۔ ثبوت پر گہری نظر ڈالنے سے پتہ چلتا ہے کہ اس سے ہمیں R [X] میں GCDs کے وجود کو ثابت کرنے میں مدد ملتی ہے، اگر وہ R اور F [X] میں موجود ہیں۔ خاص طور پر، اگر GCDs R میں موجود ہیں، اور اگر X کو ایک متغیر تک کم کر دیا گیا ہے، تو یہ ثابت کرتا ہے کہ GCDs R [X] میں موجود ہیں (یوکلڈ کا الگورتھم F [X] میں GCDs کے وجود کو ثابت کرتا ہے)۔ n متغیرات میں ایک کثیر الجہتی کو (n−1) متغیرات میں کثیر الجہتی کی انگوٹی پر ایک غیر متغیر کثیر الجہتی سمجھا جا سکتا ہے۔ اس طرح متغیرات کی تعداد پر تکرار سے پتہ چلتا ہے کہ اگر GCD موجود ہیں اور R میں ان کا حساب لگایا جا سکتا ہے، تو وہ موجود ہیں اور R پر ہر ملٹی ویریٹ کثیر الجہتی رنگ میں ان کا حساب لگایا جا سکتا ہے۔ خاص طور پر، اگر R یا تو انٹیجرز کا رنگ ہے یا فیلڈ، تو GCDs R [x1,., xn] میں موجود ہیں، اور جو پہلے ہوتا ہے وہ ان کا حساب لگانے کے لیے ایک الگورتھم فراہم کرتا ہے۔ یہ ثبوت کہ ایک منفرد فیکٹرائزیشن ڈومین پر ایک کثیر الجہتی رنگ بھی ایک منفرد فیکٹرائزیشن ڈومین ہے اسی طرح کا ہے، لیکن یہ کوئی الگورتھم فراہم نہیں کرتا ہے، کیونکہ کسی فیلڈ پر غیر متغیر کثیر الجہتی کو فیکٹر کرنے کے لیے کوئی عمومی الگورتھم نہیں ہے (ایسی فیلڈز کی مثالیں موجود ہیں جن کے لیے غیر متغیر کثیر الجہتی کے لیے کوئی فیکٹرائزیشن الگورتھم موجود نہیں ہے)۔ اس حصے میں، ہم ایک انٹیگرل ڈومین Z (عام طور پر انٹیجرز کی رنگ Z) اور اس کے فریکشنز کے فیلڈ Q (عام طور پر عقلی نمبروں کا فیلڈ Q) پر غور کرتے ہیں۔ غیر متغیر کثیر الجہتی رنگ Z [X] میں دو کثیر الجہتی A اور B کو دیکھتے ہوئے، B کے ذریعہ A کی یوکلڈین تقسیم (Q پر) ایک حصص اور ایک بقیہ فراہم کرتی ہے جس کا تعلق Z [X] سے نہ ہو۔ کیونکہ، اگر کوئی یوکلڈ کے الگورتھم کو درج ذیل کثیر الجہتی پر لاگو کرتا ہے اور یوکلڈ کے الگورتھم کے یکے بعد دیگرے باقی رہ جانے والے یہ ہیں کہ ایک دیکھتا ہے کہ، ان پٹ کثیر الجہتی کے کوفیشنٹس کی چھوٹی ڈگری اور چھوٹے سائز کے باوجود، کسی کو بڑے سائز کے انٹیجر فریکشنز کو جوڑنا اور آسان بنانا پڑتا ہے۔ فرضی تقسیم کو یوکلڈ کے الگورتھم کی ایک قسم کی اجازت دینے کے لیے متعارف کرایا گیا ہے جس کے لیے تمام بقیہ Z [X] سے تعلق رکھتے ہیں۔ اگر اور a اور b، B کے ذریعہ A کی فرضی تقسیم کا فرضی بقیہ، جسے پریم (A، B) سے ظاہر کیا جاتا ہے، وہ ہے جہاں B کا اہم گتانک (Xb کا گتانک) ہے۔ Z [X] میں دو کثیر الجہتی کی چھدم تقسیم کا چھدم باقی ہمیشہ Z [X] سے تعلق رکھتا ہے۔ ایک فرضی بقیہ ترتیب (فرضی) بقیہ ری کی ترتیب ہے جو یوکلڈ کے الگورتھم کی ہدایت کو تبدیل کرکے حاصل کی جاتی ہے جہاں α Z کا ایک عنصر ہے جو عدد کے بالکل ہر گتانک کو تقسیم کرتا ہے۔ α کے مختلف انتخاب مختلف سڈو-ریمینڈر ترتیب دیتے ہیں، جو اگلے ذیلی حصوں میں بیان کیے گئے ہیں۔ چونکہ دو کثیر الجہتی کے مشترکہ تقسیم کاروں کو تبدیل نہیں کیا جاتا ہے اگر کثیر الجہتی کو الٹا مستقل (ق میں) سے ضرب دی جائے تو، چھدم-باقی ترتیب میں آخری غیر صفر اصطلاح ان پٹ کثیر الجہتی کا جی سی ڈی (ق [X] میں) ہے۔ لہذا، سڈو ریمینڈر سیکوینسز ق میں فریکشن متعارف کرائے بغیر ق [ایکس] میں جی سی ڈی کی کمپیوٹنگ کی اجازت دیتا ہے۔ کچھ سیاق و سباق میں، چھدم باقی رہنے والے کے سرکردہ گتانک کی علامت کو کنٹرول کرنا ضروری ہے۔ یہ عام طور پر اس صورت میں ہوتا ہے جب نتائج اور ذیلی نتائج کا حساب لگایا جاتا ہے، یا اسٹرم تھیوریم کا استعمال کیا جاتا ہے۔ یہ کنٹرول یا تو سیڈو ریمینڈر کی تعریف میں اس کی مطلق قدر سے تبدیل کر کے، یا کے نشان کو کنٹرول کر کے کیا جا سکتا ہے (اگر بقیہ کے تمام کوفشنٹس کو تقسیم کرتا ہے، تو یہ اس کے لیے بھی درست ہے)۔ ٹریویل سیوڈو ریمینڈر سیکوینس سب سے آسان (وضاحت کرنے کے لیے) بقیہ سیکوینس ہمیشہ لینے پر مشتمل ہوتا ہے۔ عملی طور پر، یہ دلچسپ نہیں ہے، کیونکہ کوفشنٹس کا سائز ان پٹ کثیر الجہتی کی ڈگری کے ساتھ تیزی سے بڑھتا ہے۔ یہ پچھلے حصے کی مثال پر واضح طور پر ظاہر ہوتا ہے، جس کے لیے یکے بعد دیگرے سڈو ریمینڈرز ہوتے ہیں۔ الگورتھم کے ہر تکرار پر یکے بعد دیگرے بقیہ کے کوفیشنٹس کے ہندسوں کی تعداد دوگنی سے زیادہ ہوتی ہے۔ یہ معمولی سیڈو ریمینڈر ترتیبات کا عام طرز عمل ہے۔ ابتدائی سڈو-ریمینڈر ترتیب ابتدائی سڈو-ریمینڈر ترتیب α کے لیے عدد کے مواد کو لینے پر مشتمل ہوتی ہے۔ اس طرح تمام ری ابتدائی کثیر الجہتی ہیں۔ ابتدائی سڈو-ریمینڈر ترتیب سڈو-ریمینڈر ترتیب ہے، جو سب سے چھوٹے کوفیشنٹس پیدا کرتی ہے۔ تاہم اس کے لیے Z میں متعدد GCD کا حساب لگانے کی ضرورت ہوتی ہے، اور اس لیے عملی طور پر استعمال کرنے کے لیے کافی موثر نہیں ہے، خاص طور پر جب Z خود ایک کثیر الجہتی رنگ ہو۔ پچھلے حصوں کی طرح ہی ان پٹ کے ساتھ، ان کے مواد کے لحاظ سے تقسیم کے بعد، یکے بعد دیگرے بقیہ ہوتے ہیں۔ کوفیشنٹس کا چھوٹا سائز اس حقیقت کو چھپاتا ہے کہ جی سی ڈی کے ذریعہ متعدد انٹیجرز جی سی ڈی اور ڈویژنوں کا حساب لگایا گیا ہے۔ سب ریسلٹنٹ سیوڈو ریمینڈر سیکوینس ایک سب ریسلٹنٹ سیکوینس کا حساب سیوڈو ریمینڈرز کے ساتھ بھی لگایا جا سکتا ہے۔ یہ عمل α کو اس طرح منتخب کرنے پر مشتمل ہے کہ ہر ری ایک ذیلی نتیجہ خیز کثیر الجہتی ہو۔ حیرت انگیز طور پر، α کا حساب لگانا بہت آسان ہے (نیچے دیکھیں)۔ دوسری طرف، الگورتھم کی درستگی کا ثبوت مشکل ہے، کیونکہ اس میں مسلسل دو بقیہ ڈگریوں کے فرق کے تمام امکانات کو مدنظر رکھنا چاہیے۔ سب ریسلٹنٹ سیکوینس میں کوفیشنٹس شاذ و نادر ہی ابتدائی سیڈو ریمینڈر سیکوینس سے بہت بڑے ہوتے ہیں۔ چونکہ Z میں GCD کمپیوٹیشن کی ضرورت نہیں ہے، اس لیے سیڈو ریمینڈرز کے ساتھ ذیلی نتیجہ خیز ترتیب سب سے زیادہ موثر کمپیوٹیشن فراہم کرتی ہے۔ پچھلے حصوں کی طرح ہی ان پٹ کے ساتھ، یکے بعد دیگرے بقیہ ہیں۔ کوفیشنٹس کا سائز معقول ہوتا ہے۔ وہ کسی بھی جی سی ڈی کے حساب کے بغیر حاصل کیے جاتے ہیں، صرف عین مطابق تقسیم۔ یہ اس الگورتھم کو ابتدائی سڈو ریمینڈر ترتیبات سے زیادہ موثر بناتا ہے۔ ذیلی نتیجہ کی ترتیب کو سیڈو ریمینڈرز کے ساتھ کمپیوٹنگ کرنے والا الگورتھم ذیل میں دیا گیا ہے۔ اس الگورتھم میں، ان پٹ Z [X] میں کثیر الجہتی کا ایک جوڑا ہے۔ Z [X] میں یکے بعد دیگرے چھدم بقیہ ہیں، متغیر i اور غیر منفی عدد ہیں، اور یونانی حروف Z میں عناصر کی نشاندہی کرتے ہیں۔ افعال ڈیگ () اور ریم () کثیر الجہتی کی ڈگری اور یوکلڈین تقسیم کے بقیہ کو ظاہر کرتے ہیں۔ الگورتھم میں، یہ بقیہ ہمیشہ Z [X] میں ہوتا ہے۔ آخر میں جن تقسیموں کی نشاندہی کی جاتی ہے وہ ہمیشہ درست ہوتے ہیں اور ان کا نتیجہ Z [X] یا Z میں ہوتا ہے۔ نوٹ: "ایل سی" کا مطلب معروف گتانک ہے، جو متغیر کی اعلی ترین ڈگری کا گتانک ہے۔ یہ الگورتھم نہ صرف سب سے بڑے مشترکہ تقسیم کنندہ (آخری غیر صفر) کا حساب لگاتا ہے، بلکہ تمام ذیلی نتیجہ خیز کثیر الجہتی کا بھی حساب لگاتا ہے: بقیہ-th ذیلی نتیجہ خیز کثیر الجہتی ہے۔ اگر،-th ذیلی نتیجہ کثیر الجہتی ہے۔ دیگر تمام ذیلی نتیجہ خیز کثیر الجہتی صفر ہیں۔ سڈو-ریمینڈرز کے ساتھ سٹرم سیکوینس سٹرم سیکوینسز جیسی ہی خصوصیات والے سیکوینسز کی تعمیر کے لیے سڈو-ریمینڈرز کا استعمال کر سکتا ہے۔ اس کے لیے مسلسل سڈو ریمینڈرز کی علامتوں کو کنٹرول کرنے کی ضرورت ہوتی ہے، تاکہ وہی علامات ہوں جو اسٹرم ترتیب میں ہیں۔ یہ ایک ترمیم شدہ سڈو ریمینڈر کی وضاحت کے ذریعے کیا جا سکتا ہے۔ اگر اور a اور b، تو B کے ذریعہ A کی فرضی تقسیم کا ترمیم شدہ فرضی-ریمینڈر پریم 2 (A، B) ہے جہاں |lc (B) | B کے معروف گتانک (Xb کا گتانک) کی مطلق قیمت ہے۔ ان پٹ کثیر الجہتی کے لیے انٹیجر کوفیشنٹس کے ساتھ، یہ انٹیجر کوفیشنٹس کے ساتھ کثیر الجہتی پر مشتمل اسٹرم سیکوینس کی بازیافت کی اجازت دیتا ہے۔ سب ریسلٹنٹ سیوڈو ریمینڈر سیکوینس میں بھی اسی طرح ترمیم کی جا سکتی ہے، اس صورت میں بقیہ اشارے ان کے ساتھ موافق ہوتے ہیں جو عقلی پر شمار کیے جاتے ہیں۔ نوٹ کریں کہ سب ریسلٹنٹ سیوڈو ریمینڈر سیکوینس کو کمپیوٹ کرنے کے لیے اوپر دیا گیا الگورتھم غلط سب ریسلٹنٹ کثیر الجہتی کا حساب لگائے گا اگر کوئی اس کے بجائے استعمال کرتا ہے۔ ماڈیولر GCD الگورتھم اگر f اور g F [x] میں کسی حتمی طور پر تیار کردہ فیلڈ F کے لیے کثیر الجہتی ہیں، تو یوکلڈین الگورتھم ان کے GCD کا حساب لگانے کا سب سے قدرتی طریقہ ہے۔ تاہم، جدید کمپیوٹر الجبرا سسٹم اسے صرف اس صورت میں استعمال کرتے ہیں جب F ایک رجحان کی وجہ سے محدود ہو جسے انٹرمیڈیٹ ایکسپریشن سویل کہا جاتا ہے۔ اگرچہ یوکلڈین الگورتھم کے دوران ڈگریاں کم ہوتی رہتی ہیں، اگر F محدود نہیں ہے تو گنتی کے دوران کثیر الجہتی کا بٹ سائز (بعض اوقات ڈرامائی طور پر) بڑھ سکتا ہے کیونکہ F میں بار بار ریاضی کی کارروائیاں بڑے تاثرات کا باعث بنتی ہیں۔ مثال کے طور پر، دو عقلی اعداد کا اضافہ جن کے ڈینومینیٹرز b سے جڑے ہوتے ہیں ایک عقلی نمبر کی طرف لے جاتا ہے جس کا ڈینومینیٹر b2 سے جڑا ہوتا ہے، لہذا بدترین صورت میں، بٹ کا سائز صرف ایک آپریشن کے ساتھ تقریبا دگنا ہو سکتا ہے۔ حساب کو تیز کرنے کے لیے، ایک رنگ D لیں جس کے لیے f اور g D [x] میں ہوں، اور ایک آئیڈیل I اس طرح لیں کہ D/I ایک محدود رنگ ہو۔ پھر یوکلڈین الگورتھم کے ساتھ اس محدود رنگ پر جی سی ڈی کا حساب لگائیں۔ تعمیر نو کی تکنیکوں کا استعمال (چینی بقیہ تھیوریم، عقلی تعمیر نو، وغیرہ) f اور g کی GCD کو اس کے امیج ماڈیولو سے متعدد آئیڈیل I سے بازیافت کیا جا سکتا ہے۔ کوئی یہ ثابت کر سکتا ہے کہ یہ کام کرتا ہے بشرطیکہ کوئی غیر کم سے کم ڈگری کے ساتھ ماڈیولر امیجز کو مسترد کرتا ہے، اور آئیڈیل I ماڈیولو سے گریز کرتا ہے جس سے ایک معروف گتانک غائب ہو جاتا ہے۔ فرض کریں، اور۔ اگر ہم لیتے ہیں تو یہ ایک محدود رنگ ہے (کوئی فیلڈ نہیں کیونکہ یہ زیادہ سے زیادہ نہیں ہے)۔ یوکلڈین الگورتھم کا اطلاق ان کی تصاویر پر ہوتا ہے جو کامیاب ہوتا ہے اور 1 واپس کرتا ہے۔ اس کا مطلب یہ ہے کہ ان کا جی سی ڈی بھی 1 ہونا چاہیے۔ نوٹ کریں کہ اس مثال کو آسانی سے کسی بھی طریقے سے سنبھالا جا سکتا ہے کیونکہ ڈگریاں اظہار کے ہونے کے لیے بہت چھوٹی تھیں، لیکن اس سے یہ ظاہر ہوتا ہے کہ اگر دو کثیر الجہتی میں جی سی ڈی 1 ہے، تو ماڈیولر الگورتھم کے ایک آئیڈیل کے بعد ختم ہونے کا امکان ہے۔ یہ بھی دیکھیں کثیر الجہتی موضوعات کی فہرست کثیر متغیر تقسیم الگورتھم حوالہ جات کثیر الجہتی کمپیوٹر الجبرا