Obliczyć nwd pewniych liczb m, n

[Zaratustra]

Witam znowu
Siedzę nad tak sformułowanym zadaniem:
Oblicz:
(a) \(\displaystyle{ \hbox{NWD}(n, n+1)}\)
(b) \(\displaystyle{ \hbox{NWD}(n, n+2)}\)
(c) \(\displaystyle{ \hbox{NWD}(m+2n, 2m+n)}\), gdzie \(\displaystyle{ \hbox{NWD}(m, n)=1}\)

Pierwsze dwa podpunkty prosiłbym o sprawdzenie(szczególnie podejście do drugiego), z trzecim... coś tam wymęczyłem

(a) Liczę algorytmem euklidesa jak dla jawnie zadanych liczb:
\(\displaystyle{ n + 1 = 1 \cdot n + 1}\)
\(\displaystyle{ n = n \cdot 1 + 0}\)
Ostatnia niezerowa reszta równa \(\displaystyle{ 1}\) jest nwd obydwóch liczb zatem
\(\displaystyle{ \hbox{NWD}(n, n+1) = 1}\)

(b) Tutaj liczenie w podobny sposób prowadziło do kwiatków; głównie z tą dwójką.
Spróbowałem rozpatrzyć dwa przypadki:
(1) Dla \(\displaystyle{ n = 2k; k \in \mathbb{Z}}\)
\(\displaystyle{ n + 2 = 1 \cdot n + 2}\)
\(\displaystyle{ n = k\cdot2 + 0}\)
Ponownie ostatnia niezerowa reszta równa \(\displaystyle{ 2}\) będzie nwd obydwóch liczb.
(2) Dla \(\displaystyle{ n=2k + 1; k \in \mathbb{Z}}\)
\(\displaystyle{ n + 2 = 1 \cdot n + 2}\)
\(\displaystyle{ n = 2 \cdot k + 1}\)
\(\displaystyle{ k = k \cdot 1 + 0}\)
Ostatnia niezerowa reszta jest równa \(\displaystyle{ 1}\)
To by ostatecznie dawało następującą odpowiedź:
Dla \(\displaystyle{ n=2k; k \in \mathbb{Z}}\) jest \(\displaystyle{ \hbox{NWD}(n, n+2)=2}\)
Dla \(\displaystyle{ n=2k+1; k \in \mathbb{Z}}\) jest \(\displaystyle{ \hbox{NWD}(n, n+2)=1}\)

I teraz:
(c) To oczywiście dla mnie trochę mniej trywialne . i pultam się w rachunkach:
\(\displaystyle{ m+2n=1 \cdot (2m+n) + (n - m)}\)
\(\displaystyle{ 2m + n = (n - m) + 3m}\)
\(\displaystyle{ n - m = 3m + (-4m)}\)
\(\displaystyle{ 3m = (-1)(-4m) - m}\)
\(\displaystyle{ -4m = (-4)m + 0}\)
Więc twierdzę, że \(\displaystyle{ \hbox{NWD}(m+2n, 2m+n) = -m}\) Coś mi nie pasi.
I nie bardzo potrafię tu zrobić sprawdzenie.

Jeszcze powalczę ale jak poprzednio: byłbym wdzięczny za wskazówki, w ogóle czy obrana droga jest dobra, czy może tylko w rachunkach(np. w tym ostatnim) się mylę...


P.S. Myślałem czy nie zgrabniej rozpisywać z własności nwd:
\(\displaystyle{ \hbox{NWD}(a, b)=\hbox{NWD}(b, r)}\) gdzie \(\displaystyle{ r=a \mod b}\)
ale to w gruncie rzeczy jest dalej stosowanie tego samego algorytmu, chociaż może bardziej by było widać o co chodzi w rachunkach... Co jest resztą, ilorazem, itd.

[Premislav]

a) i b) masz poprawnie.
c) proponowałbym zacząć od tego, że bez straty ogólności np. \(\displaystyle{ m<n}\).
Trzecia linijka:

\(\displaystyle{ n - m = 3m + (-4m)}\)

tu jest jakiś błąd, tak nie wychodzi. Powinno być przecież
\(\displaystyle{ n-m=3m+(n-4m)}\)

[Zaratustra]

Trzecia linijka:

\(\displaystyle{ n - m = 3m + (-4m)}\)

tu jest jakiś błąd, tak nie wychodzi. Powinno być przecież
\(\displaystyle{ n-m=3m+(n-4m)}\)

Tak, chwilę potem jak jeszcze raz liczyłem, to zauważyłem :-/ Ale od tego miejsca obliczenia i tak zaczynają się "pętlić".
Przeszło mi przez myśl takie założenie \(\displaystyle{ m<n}\) ale i tak nie pozwala to nic powiedzieć o \(\displaystyle{ m+2n, 2m+n}\)(która większa/mniejsza) a nic innego to (dla mnie, na razie) nie wniosło.

Próbowałem jeszcze jakoś skorzystać z założenia \(\displaystyle{ \hbox{NWD}(m, n) = 1}\), np. trochę chaotycznie próbować twierdzeń typu "\(\displaystyle{ \hbox{NWD}(a, b) = d \Leftrightarrow \exists x, y \in \mathbb{Z}. d = ax + by}\)"(chociaż wprowadzenie dwóch nowych zmiennych nie wydaje się zbyt pomocne ) Ale jeszcze powalczę :P to może coś sam wymyślę.

[Chewbacca97]

A może tak?

\(\displaystyle{ d=\hbox{NWD}\left( m+2n, 2m+n\right)}\) jest nieparzysta, bo w przeciwnym razie: \(\displaystyle{ 2| m+2n \Rightarrow 2|m}\) i \(\displaystyle{ 2|2m+n \Rightarrow 2|n}\) , a to prawdą być nie może, bo \(\displaystyle{ \hbox{NWD}\left( m,n\right) =1}\).

Mamy teraz: \(\displaystyle{ d|m+2n}\) i \(\displaystyle{ d|2m+n}\). Wynika stąd, że \(\displaystyle{ d|m-n}\) i \(\displaystyle{ d|m+n}\). A stąd, że \(\displaystyle{ d|m}\) i \(\displaystyle{ d|n}\).

Czyli: \(\displaystyle{ d|\hbox{NWD}\left( m,n\right) \Rightarrow d|1 \Rightarrow d=1}\).

Chyba, że gdzieś przekłamałem...

[Zaratustra]

Mamy teraz: \(\displaystyle{ d|m+2n}\) i \(\displaystyle{ d|2m+n}\). Wynika stąd, że \(\displaystyle{ d|m-n}\) i \(\displaystyle{ d|m+n}\). A stąd, że \(\displaystyle{ d|m}\) i \(\displaystyle{ d|n}\).

Wygląda poprawnie(ta nieparzystość też jest ok.)... trochę bardziej sobie rozpisałem i chyba w porządku.
Wtedy oczywiście końcówka daje rozwiązanie:

Czyli: \(\displaystyle{ d|\hbox{NWD}\left( m,n\right) \Rightarrow d|1 \Rightarrow d=1}\).

Muszę się jeszcze doszlifować, bo na przykład tu utkwiłem :-/

W każdym razie dzięki za pomoc ;]