Страницата на Барнабас Харастос

Останалите 0, алгоритъмът приключи. Най-големият обикновен дилър последният ненулев остатък - в нашия случай 3.

дясната страна

Възникват два важни въпроса (както при всички алгоритми):

  1. Сигурен ли е алгоритъмът да приключи?
  2. Наистина ли предоставя това, което очаквахме? (A lnko-t.)

Отговор на въпрос 1: Тъй като остатъкът в остатъчното деление винаги е по-малък от делителя, \ [b> m_1> m_2> m_3> m_4 \ ldots, \] т.е.последователността на остатъците е строго монотонна. Тъй като в \ (\ mathbb N \) под \ (b \) има само крайно число (по-специално \ (b \) db), тази загуба на тегло не може да продължи безкрайно. В противен случай не може да спре, само така че останалите 0 \ (\ Longrightarrow \) от алгоритъма да завършат (терминал).

Отговор на въпрос 2: Вече е по-трудно. Защо последният ненулев остатък (\ (m_k \)) ще бъде най-големият общ делител на първоначалните две числа (\ (a \) и \ (b \))?

2.1. изявление: Последният ненулев остатъчен общ делител: Напишете останалите деления под формата на продукт и след това разберете кой от числата е разделен на последния ненулев остатък, \ (m_k \).

(Фигурата показва това в алгоритъм, завършващ на 6 стъпки: щракването върху него подчертава числата, разделени на последния ненулев остатък, в нашия случай \ (m_5 \).

(2) В последния ред \ (m_5 \) се умножава по \ (h_6 \) до \ (m_4 \), което също разделя \ (m_4 \). (Щракнете!)

(3) Последният ред се оказа, че разделя \ (m_4 \) и \ (m_5 \) на пет \ (m_5 \).
Нека прехвърлим тези знания на предпоследния ред! (Кликнете върху изображението!)

(4) От дясната страна на предпоследния ред и двата термина могат да бъдат разделени на \ (m_5 \), така че \ (m_3 \) също могат да бъдат разделени от него. (Кликнете върху изображението!)