الگوریتم هایی برای محاسبه بزرگترین مقسوم علیه مشترک و کاربرد آنها در حل معادلات دیوفانتی خطی

یکی از مراحل مهم در حل دستگاههای دیوفانتی خطی، محاسبه بزرگترین مقسوم علیه مشترک چند عدد صحیح است. الگوریتم اقلیدس اغلب به عنوان یکی از الگوریتم های موثر برای محاسبه بزرگترین مقسوم علیه مشترک دو عدد صحیح استفاده می شود. با ادغام الگوریتم اقلیدس با یک روند تکراری می توان آن را برای محاسبه بزرگترین مقسوم علیه مشترک چند عدد صحیح نیز به کار برد. در این مقاله به بررسی چند الگوریتم برای محاسبه بزرگترین مقسوم علیه مشترک شماری متناهی از اعداد صحیح همراه با چگونگی محاسبه جواب عمومی تک معادله های دیوفانتی خطی می پردازیم.

Keywords:

بزرگتریم مقسوم علیه مشترک , دستگاه معادلات دیوفانتی , الگوریتم اقلیدس , ماتریس تک - مدولی