Algorytm Euklidesa.

[1991Kamil]

Mam kilka zadań z algorytmem Euklidesa. Prosiłbym o pomoc w ich rozwiązaniu.

1) Załóżmy, że \(\displaystyle{ a < b}\) oraz, że algorytm Euklidesa wykonał \(\displaystyle{ k}\) kroków przy wyznaczaniu \(\displaystyle{ NWD(a,b)}\). Wykaż, że \(\displaystyle{ a \ge F_{k}}\) i \(\displaystyle{ b \ge F_{k+1}}\)

2) Stosując algorytm Euklidesa znajdź \(\displaystyle{ NWD(100, 54)}\).

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

rozw:

Zrobiłem tylko zad. 3. Na pozostałe nie mam pomysłu.

3)
\(\displaystyle{ 100 : 54 = 1}\), r. \(\displaystyle{ 46}\)
\(\displaystyle{ 54 : 46 = 1}\), r. \(\displaystyle{ 8}\)
\(\displaystyle{ 46 : 8 = 5}\), r. \(\displaystyle{ 6}\)
\(\displaystyle{ 8 : 6 = 1}\), r. \(\displaystyle{ 2}\)
\(\displaystyle{ 6 : 2 = 3}\), r. \(\displaystyle{ 0}\)

\(\displaystyle{ NWD(100, 54) = 2}\)

[anna_]

3)
\(\displaystyle{ 256 : 100 = 2}\), r \(\displaystyle{ 56}\)
\(\displaystyle{ 100 : 56 = 1}\), r \(\displaystyle{ 44}\)
\(\displaystyle{ 56 : 44 = 1}\), r \(\displaystyle{ 12}\)
\(\displaystyle{ 44 : 12 = 3}\), r \(\displaystyle{ 8}\)
\(\displaystyle{ 12 : 8 = 1}\), r \(\displaystyle{ 4}\)
\(\displaystyle{ 8 : 4 = 2}\), r \(\displaystyle{ 0}\)


\(\displaystyle{ NWD(256, 100)=4}\)

[1991Kamil]

Sorry, pomyliłem się. Moje "trzecie" tak naprawdę miało być drugie. To moje rozwiązanie jest dobre? Są jeszcze jakieś inne sposoby na rozwiązanie tego zadania?

A co do zadania, które rozwiązała Ania to czy to jest jedyny sposób (też zastanawiałem się nad nim)? Trzeba po kolei próbować każdą parę liczb aż się coś "trafi" czy da się to jakoś szybciej wyznaczyć? Przypuśćmy, że takie zadanko będzie na jakimś sprawdzianie a tam jest ograniczony czas itd.

[anna_]

Twoje rozwiązanie jest dobre.

To trzecie można robić od końca.
Bierzesz np liczbę \(\displaystyle{ 5}\)i \(\displaystyle{ r=0}\) i dowolną liczbę np \(\displaystyle{ 3}\), która będzie w sumie dzielnikiem naszych liczb.
Liczymy:
\(\displaystyle{ 5 \cdot 3+0=15}\)
czyli 6 krok to:
\(\displaystyle{ \red 15:3=5 \ r \ 0}\)

Bierzemy sobie dowolną liczbę np \(\displaystyle{ 2}\) i \(\displaystyle{ r=3}\)
Liczymy:
\(\displaystyle{ 2 \cdot 15+3=33}\)
czyli 5 krok wyglądałby tak:
\(\displaystyle{ \red 33:15=2\ r \ 3}\)

Bierzemy sobie dowolną liczbę np \(\displaystyle{ 4}\) i \(\displaystyle{ r=15}\)
Liczymy:
\(\displaystyle{ 5 \cdot 33+15=180}\)
czyli 4 krok wyglądałby tak:
\(\displaystyle{ \red 180:33=5\ r \ 15}\)

Bierzemy sobie dowolną liczbę np \(\displaystyle{ 1}\) i \(\displaystyle{ r=33}\)
Liczymy:
\(\displaystyle{ 1 \cdot 180+33=213}\)
czyli 3 krok wyglądałby tak:
\(\displaystyle{ \red 213:180=1\ r \ 33}\)

Bierzemy sobie dowolną liczbę np \(\displaystyle{ 2}\) i \(\displaystyle{ r=213}\)
Liczymy:
\(\displaystyle{ 2 \cdot 213+180=606}\)
czyli 2 krok wyglądałby tak:
\(\displaystyle{ \red 606:213=2\ r \ 180}\)

Bierzemy sobie dowolną liczbę np \(\displaystyle{ 1}\) i \(\displaystyle{ r=606}\)
Liczymy:
\(\displaystyle{ 1 \cdot 606+213=819}\)
czyli 1 krok wyglądałby tak:
\(\displaystyle{ \red 819:606=1\ r \ 213}\)

[1991Kamil]

A zadanie nr 1 potrafi ktoś zrobić? Nie wiem jak się do tego zabrać. Wydaje mi się, że jeśli \(\displaystyle{ a < b}\) to nie da się podzielić tych liczb.