logowanie

matematyka » forum » studia » zadanie

Matematyka dyskretna, zadanie nr 764

ostatnie wiadomości  |  regulamin  |  latex

AutorZadanie / Rozwiązanie

natalia1992
postów: 26
2012-12-11 14:03:21

Znaleźć taką parę liczb naturalnych, dla której algorytm Euklidesa kończy się po 6 krokach.


tumor
postów: 8085
2012-12-11 16:05:03

Nawet sobie możesz wybrać NWD, jaki chcesz. :)

Na przykład NWD(a,b)=3

Po ostatnim kroku będziemy mieć (3,0)
Po przedostatnim (c,3) a chcemy, żeby liczba c dzielona przez 3 dawała resztę 0. Czyli niech jest (6,3).
Po drugim od końca (d,6) i d dzielone na 6 ma dawać resztę 3, czyli na przykład (9,6). Kolejne wyrazy tworzymy w ten sam sposób. Będzie

(3,0)
(6,3)
(9,6)
(15,9)
(24,15)
(39,24)
(63,39) - tu masz te liczby, które po sześciu krokach algorytmu Euklidesa dadzą NWD(a,b)=3. Oczywiście możesz wybierać liczby na trasie inaczej i ustalić na początku inny NWD. Jak Ci wygodnie.

strony: 1

Prawo do pisania przysługuje tylko zalogowanym użytkownikom. Zaloguj się lub zarejestruj





© 2017 Mariusz Śliwiński      o serwisie | kontakt online: 8 drukuj