"Wykaż, że" z nwd.

[Zaratustra]

Witam jeszcze raz. Może jakaś dobra dusza sprawdzić poprawność mojego rozwiązania?

Zadanie: Wykaż, że \(\displaystyle{ \hbox{NWD}(5a+4b, 4a+3b)=1}\) wtedy i tylko wtedy, gdy \(\displaystyle{ \hbox{NWD}(a, b)=1}\).
Dowód: Najpierw "w prawo". Załóżmy nie wprost, że \(\displaystyle{ \hbox{NWD}(a, b)=d > 1}\).
Ponieważ \(\displaystyle{ \hbox{NWD}(5a+4b, 4a+3b)=1}\), to mamy, że dla dowolnego \(\displaystyle{ \tilde{d} \in \mathbb{Z}}\)
jeśli \(\displaystyle{ \tilde{d}|5a+4b}\) i \(\displaystyle{ \tilde{d}|4a+3b}\), to \(\displaystyle{ \tilde{d} \leq 1}\).
Ale \(\displaystyle{ d|a}\) i \(\displaystyle{ d|b}\), zatem \(\displaystyle{ d|ma+nb}\) dla dowolnych \(\displaystyle{ m, n \in \mathbb{Z}}\), w szczególności \(\displaystyle{ |5a+4b}\) i \(\displaystyle{ d|4a+3b}\).
Ale \(\displaystyle{ d > 1}\), zatem sprzeczność.
Teraz w drugą stronę; załóżmy(ponownie nie wprost), że \(\displaystyle{ \hbox{NWD}(5a+4b, 4a+3b)=d > 1}\).
To \(\displaystyle{ d|5a+4b}\) i \(\displaystyle{ d|4a+3b}\), zatem \(\displaystyle{ d|a+b}\)(ich różnicę); \(\displaystyle{ d|b}\) i \(\displaystyle{ d|a}\).
Ale z założenia [,że \(\displaystyle{ hbox{NWD}(a, b)=1}\)], dla dowolnego \(\displaystyle{ d_0 \in \mathbb{Z}}\)
jeśli \(\displaystyle{ d_0|a}\) i \(\displaystyle{ d_0|b}\), to \(\displaystyle{ d_0 \leq 1}\) - zatem sprzeczność.
Koniec dowodu.

[Mruczek]

Jest ok, tylko troszkę przeskoczyłeś z
\(\displaystyle{ d|a+b}\) (ich różnicę); \(\displaystyle{ d|b}\) i \(\displaystyle{ d|a}\).
To \(\displaystyle{ d|a}\) wynika z \(\displaystyle{ d | 5a + 4b = 4(a + b) + a}\), a skoro \(\displaystyle{ d | a + b}\) to też \(\displaystyle{ d | b}\).