Matematyka.pl

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ć

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

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}\).

\(\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ć?

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

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

1) 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.