Jak znaleźć NWD najprościej

Arkadiusz · Post autor: **Arkadiusz** » 26 sie 2007, o 14:43

Witam szanownych Matematyków borykam się z problemem typu jak najprościej znaleźć NWD dwóch liczb załóżmy a=1615 i b=608
W przykładzie tym mam rozwiązanie wyglądające tak:
NWD(1615, 608) = NWD(608, 399) = NWD(399, 209) = NWD(209, 190) = NWD(190, 19) = NWD(19, 0) = 19
Dało się zauważyć że liczby "b" z poszczególnych nawiasów są przepisywane w miejsce liczby "a"
ale nie mogę dojść skąd się bierą liczby podkreślone w moim przykładzie
Bardzo proszę o wyjaśnienie krok po kroku (nie jestem jeszcze matematykiem więc tak łopatologicznie poproszę )

Czy są jeszcze jakieś inne sposoby na znalezienie NWD ?

Emiel Regis · Post autor: **Emiel Regis** » 26 sie 2007, o 14:46

NWD(1615, 608) = NWD(608, 399) = NWD(399, 209) = NWD(209, 190) = NWD(190, 19) = NWD(19, 0) = 19

Podkreślone liczby to są reszty z dzielenie modulo dwóch poprzednich.
Np 399 to jest reszta z dzielenia 1615 przez 608.

Arkadiusz · Post autor: **Arkadiusz** » 26 sie 2007, o 15:03

hehe dzięki - a wydawało się takie zakręcone

DEXiu · Post autor: **DEXiu** » 30 sie 2007, o 14:14

Tak tylko dopowiem w ramach ciekawostki (jeśli jeszcze tego nie wiesz), że metoda ta nosi nazwę algorytmu Euklidesa. W liceum i starszych klasach gimnazjum można ją wprowadzać tłumacząc to tak jak wyutłumaczył to Drizzt (czyli jako reszty z dzielenia), ale w młodszych klasach z reguły mówi się dzieciom, aby od większej liczby odejmowały mniejszą i tak w kółko aż w końcu obie liczby będą sobie równe i wtedy będą one równe NWD liczb początkowych. Oczywiście jest to dokładnie równoważne sprawdzaniu reszt z dzielenia, tylko że dzieci mogą jeszcze nie znać takiego pojęcia

SK8 · Post autor: **SK8** » 31 sie 2007, o 12:01

jezeli chodzi ci o najprostszy sposob to mozesz uzyc do tego funkcji GCD() z exela. wpisz =GCD(liczba1;liczba2;...liczban;).
jezeli wyswietli ci sie blad #NAZWA?(lub jakis inny) tzn ze musisz zainstalowac dodatek. kliknij Narzedzia-->Dodatki-->i zaznacz Analisis toolpack