Algorytm NWD P: Czy ktoś mógłby wytłumaczyć jak działa ten algorytm nwd z modulo? Nie zbyt to rozumiem dlaczego przypisuje się resztę z dzielenia danej liczbie Tzn nwd(a,b) a>b a = a%b i tak w kółko Nie rozumiem w jaki sposób wtedy znajdujemy ten największy dzielnik i co ma do tego reszta z dzielenia Też niezbyt rozumiem wersję gdzie odejmujemy od siebie dwie liczby a = a−b dopóki a = b wtedy to jest NWD

Adamm: Przeanalizuj działanie algorytmu Euklidesa

Adamm: Jeśli napiszesz a = bq+r gdzie 0 ≤ r < b To te liczby n które dzielą za równo a jak i b, to te same które dzielą Zarowno b oraz r. To widać z równiania a = bq+r. Więc możemy zastąpić parę (a, b) przez parę (b, r). Ma to tą własność że przy każdym kolejnym kroku reszta jest coraz mniejsza To znaczy że w skończonym czasie algorytm przestanie dawać niezerową liczbę r (czyli taką przez którą można podzielić), i dostaniemy parę (d, 0). Stąd wniosek że ta niezerowa liczba d musi być największą która dzieli zarówno a jak i b. To dowodzi istnienia gcd(a,b), oraz pozwala nam je znaleźć.

Krzysiek: https://zapodaj.net/plik-WvBd3mlZkN

P: Aa kumam, A uzasadnienie tego z odejmowaniem?

P: To wtedy analogicznie a = kb+r potem (k−1)b+r ale cały czas podzielne przez n bo b i r podzielne przez n Dobrze?