Matematyka.pl

Witam, Mam pewien problem ponieważ nie rozumiem jak dowieść poprawności algorytmu Euklidesa z odejmowaniem. We wszystkich wykładach które znalazłem dowodzi się tylko wersji z modulo.

Prosze o pomoc w dowodzie lub wskazanie miejsca gdzie pomoc taką mogę uzyskać.

Oto dowód.
Wystarczy pokazać, że \(\displaystyle{ NWD\left(a,b\right)=NWD\left(a,a-b\right)}\).
Oznaczmy przez \(\displaystyle{ d=NWD\left(a,b\right)}\). Wówczas łatwo stwierdzamy, że \(\displaystyle{ d|a}\) oraz \(\displaystyle{ d|a-b}\) a stąd \(\displaystyle{ d|NWD\left(a,a-b\right)}\).
Niech teraz \(\displaystyle{ e=NWD\left(a,a-b\right)}\). Rozumujemy analogicznie i stwierdzamy, że \(\displaystyle{ e|a}\) oraz \(\displaystyle{ e|b}\) co daje \(\displaystyle{ e|NWD\left(a,b\right)}\).
Podsumowując dostaliśmy \(\displaystyle{ d|e}\) oraz \(\displaystyle{ e|d}\), co musi oznaczać, że \(\displaystyle{ d=e}\), a to należało pokazać.