NWD dowód

[nice1233]

Hipoteza: \(\displaystyle{ NWD(a,b) = \alpha a + \beta b }\) dla pewnych \(\displaystyle{ a, b}\) dodatnich całkowitych, bo wiemy że \(\displaystyle{ NWD(-a, -b) = NWD (a,-b) = NWD(-a, b) = NWD (a,b)}\) (Pytanie nr 1. Skąd ta własność \(\displaystyle{ NWD}\) się wzięła?)

Dowód:
Niech \(\displaystyle{ S}\) będzie zbiorem dodatnich liniowych kombinacji z liczb \(\displaystyle{ a}\) i \(\displaystyle{ b}\), takich że
\(\displaystyle{ S=\{m a+n b \mid m a+ nb > 0, m, n \in \ZZ\} }\)
Krok 1. Pokażemy że \(\displaystyle{ S}\) ma element najmniejszy
Wówczas \(\displaystyle{ a > 0, a = 1\cdot a + 0\cdot b \in S}\) i \(\displaystyle{ S}\) jest zbiorem niepustym ( Pytanie nr 2. Dlaczego elementem najmniejszym jest \(\displaystyle{ a}\) nie \(\displaystyle{ b}\)? Czy to ma jakieś znaczenie w dowodzie). Wówczas na mocy zasady minimum \(\displaystyle{ S}\) jest podzbiorem liczb naturalnych zatem posiada element najmniejszy. \(\displaystyle{ S}\) ma element dodatni - \(\displaystyle{ d}\).
Krok 2. Pokażemy że \(\displaystyle{ d = (a,b)}\)

Niech \(\displaystyle{ d}\) należy do \(\displaystyle{ S}\) wówczas \(\displaystyle{ \mathrm{S}=\{\mathrm{ma}+\mathrm{nb} \mid \mathrm{ma}+\mathrm{nb}>0, \quad \mathrm{~m}, \mathrm{n} \in \ZZ\}}\) , dla pewnych liczb całkowitych \(\displaystyle{ \alpha}\) i \(\displaystyle{ \beta}\).

a) Pokażemy że \(\displaystyle{ d|a}\) i \(\displaystyle{ d|b}\).

Z własności (algorytmu dzielenia z resztą) ADR, istnieją takie \(\displaystyle{ q}\) i \(\displaystyle{ r}\) dla których \(\displaystyle{ a = dq + r}\) (P.3 Dlaczego \(\displaystyle{ d}\) musi być \(\displaystyle{ q}\) ?) gdzie \(\displaystyle{ 0 \leq r<d}\) Podstawiając za \(\displaystyle{ d}\):

\(\displaystyle{
\begin{aligned}
a = dq + r\\
r &=a-d q \\
&=a-(\alpha a+\beta b) q \\
&=(1-\alpha q) a+(-\beta q) b
\end{aligned}}\)

Pokazaliśmy że \(\displaystyle{ r}\) jest kombinacją liniową liczb \(\displaystyle{ a}\) i \(\displaystyle{ b}\).
Jeżeli \(\displaystyle{ r> 0}\) wówczas \(\displaystyle{ r}\) należy do \(\displaystyle{ S}\). Wówczas \(\displaystyle{ r < d}\), \(\displaystyle{ r}\) jest mniejsze od najmniejszego elementu w zbiorze \(\displaystyle{ S}\), co jest w sprzeczności.
Jeżeli \(\displaystyle{ r = 0}\). Wówczas \(\displaystyle{ a = dq}\) , więc \(\displaystyle{ d|a}\).
Podobnie \(\displaystyle{ d|b}\), wówczas \(\displaystyle{ d}\) jest wspólnym dzielnikiem liczb \(\displaystyle{ a, b}\).

b) Pokażemy, że każdy inny wspólny dzielnik \(\displaystyle{ d'}\) z liczb \(\displaystyle{ a, b}\) jest \(\displaystyle{ \le d.}\)

Wówczas \(\displaystyle{ d'|a}\) i \(\displaystyle{ d'|b}\) i \(\displaystyle{ d|(\alpha \cdot a + \beta \cdot b)}\) na mocy własności ADR to oznacza że \(\displaystyle{ d'|d}\).

Pytanie 4. Nie rozumiem tutaj przejścia do wniosku

Więc \(\displaystyle{ d'\leq d. }\)

Wówczas (A) i (B) wówczas \(\displaystyle{ d = (a, b)}\).