Obliczyć nwd pewniych liczb m, n
: 28 sie 2016, o 03:01
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.
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.