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ć.
Algorytm Euklidesa z Odejmowaniem
-
bakala12
- Użytkownik
- Posty: 3044
- Rejestracja: 25 mar 2010, o 15:34
- Płeć: Mężczyzna
- Lokalizacja: Gołąb
- Podziękował: 24 razy
- Pomógł: 513 razy
Algorytm Euklidesa z Odejmowaniem
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ć.
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ć.