پاسخ:
برای محاسبه‌ی (2a+3, 5a+4) از الگوریتم اقلیدس استفاده می‌کنیم.
- 5a + 4 = 2(2a + 3) + (-2)
- 2a + 3 = (-1)(a + 1) + (1 - a)
- خطا در محاسبه: الگوریتم اقلیدس به درستی اعمال نشده است. بیایید دوباره محاسبه کنیم.
الگوریتم اقلیدس به این صورت است:
- اگر b > a باشد، آنگاه (a, b) = (a, b - aq) برای q مناسب.
- در اینجا می‌توانیم بنویسیم: (2a+3, 5a+4) = (2a+3, (5a+4) - 2*(2a+3))
- = (2a+3, a-2)
- حال اگر a-2 >= 2a+3، آنگاه a <= -5 که برای a طبیعی غیرممکن است.
- پس (2a+3, a-2) = (2a+3 - (a-2)*2, a-2)
- = (7, a-2)
بنابراین (2a+3, 5a+4) = (7, a-2)
اگر a = 9، آنگاه (7, 9-2) = 7
در غیر این صورت، اگر a-2 مضرب 7 نباشد، آنگاه (7, a-2) = 1
پس جواب نهایی بستگی به مقدار a دارد.
