Matematyka dyskretna, zadanie nr 764

Autor	Zadanie / 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: 8070	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