Odpowiedź:
Sposób optymalny
Aby obliczyć NWD(a,b) wykonujemy następujące kroki:
1. Dzielimy z resztą liczbę a przez liczbę b.
2. Jeżeli reszta jest równa 0 to NWD(a,b) = b
3. Jeżeli reszta nie jest równa 0 to przypisujemy liczbie A wartość liczby B oraz liczbie B wartość otrzymanej reszty, po czym ponownie wykonujemy krok pierwszy.
No to podstawiamy to do naszych liczb
[tex]110 : 35 = 3 \text{ reszty } 5\\35: 5 = 7 \text{ reszty } 0[/tex]
NWD w tej metodzie zawsze jest równy ostatniej niezerowej reszcie czyli w tym przypadku
[tex]\operator{NWD}(110,35) = 5[/tex]
Sposób nieoptymalny
Aby obliczyć NWD(a,b) wykonujemy następujące kroki:
1. Wybieramy większą spośród dwóch posiadanych liczb
2. Od większej liczby odejmujemy mniejszą, zamieniając je na różnice.
3. Krok drugi powtarzamy do momentu otrzymania dwóch takich samych wartości
4. Jeśli od liczby A nie można już odjąć liczby B to odejmujemy od liczby B.
No dobra, to podstawiamy
[tex]\begin{matrix} \begin{array} {c|c} 110 & 35 \\ 110 - 35 = 75 & 35 \\ 75 - 35 = 40 & 35 \\ 40 - 35 = 5 & 35 \\ 5 & 35 - 5 = 30 \\ 5 & 30 - 5 = 25 \\ 5 & 25 - 5 = 20 \\ 5 & 20 - 5 = 15 \\ 5 & 15 - 5 = 10 \\ 5 & 10 - 5 = 5 \end{array} \end{matrix}[/tex]
[tex]\operator{NWD}(110,35) = 5[/tex]
Tak naprawdę sposobu nieoptymalnego z reguły się nie używa, a jeśli już to bardzo rzadko. W obydwu tych sposobach oczywiście A zarówno jak i B muszą spełniać warunek
[tex]a \neq 0 \phantom{...} b\neq 0[/tex]
Szczegółowe wyjaśnienie:
