szukanie zaawansowane
 [ Posty: 2 ] 
Autor Wiadomość
Kobieta Offline
PostNapisane: 15 paź 2012, o 16:23 
Użytkownik
Avatar użytkownika

Posty: 279
Niecha, b, c będę liczbami naturalnymi i a = cq_{1} + r_{1}, b = cq_{2} + r _{2}. Pokazac, ze NWD(a, b, c) =NWD(c, r_{1},r _{2}). Wyprowadzić stąd metodę wyznaczania NWD trzech liczb.
Góra
Mężczyzna Offline
PostNapisane: 1 sty 2013, o 16:13 
Moderator
Avatar użytkownika

Posty: 2226
Lokalizacja: Warszawa
Z lekkim opóźnieniem, ale może kogoś jeszcze zainteresuje:
Korzystając ze znanych własności NWD:
NWD \left( a, \ b, \ c \right)= NWD \left( NWD \left( a, \ c \right), \ b \right)= NWD \left( NWD \left( cq_{1}+r_{1}, \ c \right), \ b \right)=NWD \left( NWD \left( r_{1}, \ c \right), \ b \right)=NWD \left(r_{1}, \ c, \ b \right) = NWD \left( NWD \left( b, \ c \right), \ r_{1} \right)=NWD \left( NWD \left( cq_{2}+r_{2}, \ c \right), \ r_{1} \right)= NWD \left( NWD \left( r_{2}, \ c \right), \ r_{1} \right)=NWD \left( c, \ r_{1}, \ r_{2} \right)
Metoda?
BSO a \ge b \ge c. Za pomocą dowiedzionego przekształcenia przekształcamy i przemianowujemy: c_{1} = min \left(c, \ r_{1}, \ r_{2} \right), a_{1}=max \left( c, r_{1}, \ r_{2} \right), b_{1} = \left\{ c, \ r_{1}, \ r_{2} \right\}  \setminus \left\{ a_{1}, \ c_{1} \right\}. Robimy tak w kółko, aż dla pewnego i zajdzie: b_{i}=c_{i} lub c_{i}=0, wtedy:
NWD \left(a, \ b, \ c \right) = NWD \left(a_{i}, \ b_{i} \right). A na to już algorytm znany jest.
Góra
Utwórz nowy temat Odpowiedz w temacie  [ Posty: 2 ] 


 Zobacz podobne tematy
 Tytuł tematu   Autor   Odpowiedzi 
 Teoria liczb: zależności w podzielności  raszek  4
 Zadania z podzielności liczb  shep4rd  2
 Różnica cyfr pewnej liczby wynosi 5 ... Znajdź tę liczb  Tomasz B  4
 Największy wspólny dzielnik - zadanie 17  matematykiv  16
 Podzielność liczb - zadanie 29  dawid3690  2
 
Atom [Regulamin Forum] [Instrukcja LaTeX-a] [Poradnik] [F.A.Q.] [Reklama] [Kontakt]
Copyright (C) Karpatka.pl