NWD(a,b)=NWD(a-b,b)

[matih123]

Dostałem na egzaminie zadanie:
Udowodnić, że \(\displaystyle{ NWD(a,b)=NWD(a-b,b)}\) dla dowolnych liczb całkowitych a,b i nie mam zielonego pojęcia jak to wykazać i z jakich własności korzystać

[Damianito]

Ukryta treść:    

Spróbuj pokazać, że zbiór wspólnych dzielników liczb \(\displaystyle{ a,b}\) jest taki sam jak zbiór wspólnych dzielników liczb \(\displaystyle{ a-b,b}\), a wtedy największe elementy są te same (czyli podana równość z \(\displaystyle{ NWD}\))

[matih123]

zn mogę podać 2 liczby np 60 i 15 i na ich podstawie to udowodnić?

[Errichto]

Nie, trzeba to zrobić dla dowolnych \(\displaystyle{ a}\) i \(\displaystyle{ b}\).
1) Pokaż, że skoro NWD jest dzielnikiem \(\displaystyle{ a}\) oraz \(\displaystyle{ b}\), to jest dzielnikiem \(\displaystyle{ a-b}\).
2) Pokaż, że jeśli liczby \(\displaystyle{ a-b}\) i \(\displaystyle{ b}\) mają wspólny dzielnik \(\displaystyle{ c}\), to \(\displaystyle{ c}\) jest też dzielnikiem \(\displaystyle{ a}\).

[matih123]

\(\displaystyle{ NWD(a,b)=NWD(a-b,b)}\)
\(\displaystyle{ d=NWD(a,b)}\)
\(\displaystyle{ d|a i d|b}\)
\(\displaystyle{ a=dk}\) i \(\displaystyle{ b=ld}\) czyli \(\displaystyle{ a-b=d(k-l)}\) wiec \(\displaystyle{ d|a-b}\)
Mamy \(\displaystyle{ d|a-b}\) i \(\displaystyle{ d|b}\) czyli \(\displaystyle{ d<a-b}\) i \(\displaystyle{ d<b}\)
wiec \(\displaystyle{ c=NWD(a-b,b)}\)
\(\displaystyle{ a-b=kc}\) i \(\displaystyle{ b=lc}\) wiec \(\displaystyle{ a=a-b+b=c(k-l)}\) czyli \(\displaystyle{ c|a}\) co daje \(\displaystyle{ c<a-b}\) i \(\displaystyle{ c<a}\)

\(\displaystyle{ d|a}\) implikuje \(\displaystyle{ d<a}\)

\(\displaystyle{ d|a-b}\) i \(\displaystyle{ d|a}\) i \(\displaystyle{ d|b}\)
\(\displaystyle{ c|a-b}\) i \(\displaystyle{ c|a}\) i \(\displaystyle{ c|b}\)

wiec

\(\displaystyle{ NWD(a,b)}\) --> \(\displaystyle{ d<NWD(a-b,b)}\)
\(\displaystyle{ NWD(a-b,b)=c<NWD(a,b)}\)
może tak być?

[Errichto]

\(\displaystyle{ 5|5}\) a nie zachodzi \(\displaystyle{ 5<5}\)

[matih123]

zn d\(\displaystyle{ \le}\) a i po sprawie?

[Errichto]

1)

Ukryta treść:    

zał.:
\(\displaystyle{ p|a \ \wedge \ p|b}\)
teza:
\(\displaystyle{ p|(a+b)}\)
dowód:
\(\displaystyle{ \bigvee\limits_{k,l \in C}(kp=a \ \wedge \ lp=b)}\)
\(\displaystyle{ a+b=p(k+l) \ (k+l) \in C}\)
\(\displaystyle{ p|(a+b)}\) c.n.d.

2) (część właściwa)
zał.:
\(\displaystyle{ d=NWD(a,b)}\)
teza:
\(\displaystyle{ d=NWD(a-b,b)}\)
dowód:
\(\displaystyle{ d|a \ \wedge \ d|b}\)
\(\displaystyle{ d|a \ \wedge \ d|(-b)}\)
Korzystamy z 1)
\(\displaystyle{ d|(a+(-b))}\)
\(\displaystyle{ d|(a-b) \ \wedge \ d|a}\) (A)
Na mocy 1):
\(\displaystyle{ (p|(a-b) \ \wedge \ p|b) \rightarrow p|a}\)
Czyli dowolny wspólny dzielnik liczb \(\displaystyle{ a-b}\) i \(\displaystyle{ b}\) jest też dzielnikiem \(\displaystyle{ a}\). (B)
Z (A) mamy, że \(\displaystyle{ d}\) jest wspólnym dzielnikiem \(\displaystyle{ a-b}\) i \(\displaystyle{ b}\). Z (B) mamy, że wszystkie dzielniki tych dwóch liczb są też dzielnikami \(\displaystyle{ a}\) i \(\displaystyle{ b}\) czyli żaden wspólny dzielnik pierwszych dwóch liczb nie jest większy niż największy wspólny ostatnich dwóch. Więc nie ma wspólnego dzielnika \(\displaystyle{ a-b}\) i \(\displaystyle{ b}\) większego od \(\displaystyle{ d}\). Więc \(\displaystyle{ NWD(a-b,b)=d}\) c.n.d.

Trochę pogmatwałem z tym ostatnim zdaniem, podsumowującym. Ale chyba mniej więcej jest ok.