Witajcie! Mam kłopot z pewnym zadaniem z książki pana A. Neugebauera.
Oto jego treść:
Udowodnić przez indukcje względem \(\displaystyle{ n, m \ge 0}\), że jeżeli liczby całkowite \(\displaystyle{ a, b}\) są względnie pierwsze, to \(\displaystyle{ \mathrm{NWD} (a^n, b^m) = 1}\) dla dowolnych \(\displaystyle{ n, m \in \mathbb{Z_\ge} _{0}}\).
Nie rozumiem, jak przeprowadzić tutaj indukcję względem dwóch zmiennych. Czytałem podobne wątki o takich przypadkach, ale wciąż nie wiem, jak się za to zabrać. Macie jakieś wskazówki jak do tego podejść?
Próbowałem do tej pory udowodnić \(\displaystyle{ \mathrm{NWD} (a^n, b) = 1}\) dla dowolnego \(\displaystyle{ n \in \mathbb{N}}\), a następnie przez indukcję dla dowolnego \(\displaystyle{ m \in \mathbb{N}}\), ale nie sądzę, żeby to był sposób, który miał na myśli autor, pisząc to zadanie (a może jednak tak?).
Dodam jeszcze, że zadanie to znajduje się w podrozdziale dotyczącym twierdzenia Gaussa-Bézouta (\(\displaystyle{ a \perp b}\) wtedy i tylko wtedy, gdy istnieją takie \(\displaystyle{ x, y \in \mathbb{Z}}\), że \(\displaystyle{ 1 = ax + by}\)), więc zakładam, że powinienem je wykorzystać.
Ustalmy dowolne \(\displaystyle{ a,b}\) całkowite względnie pierwsze (od razu ustalmy, że różne od zera, żeby nie było zamieszania). Przez \(\displaystyle{ T(n,m)}\) będziemy rozumieli \(\displaystyle{ \NWD(a^b, b^m)=1}\). Oczywiście \(\displaystyle{ T(0,0)}\) jest spełnione nawet bez założenia o liczbach względnie pierwszych, podobnie \(\displaystyle{ T(0,1), \ T(1,0)}\), a wprost z naszego założenia o liczbach względnie pierwszych wynika \(\displaystyle{ T(1,1)}\). Niech teraz \(\displaystyle{ m,n\ge 1}\).
Wykażemy, że \(\displaystyle{ T(n,m)}\) pociąga \(\displaystyle{ T(n+1, m)}\). Istotnie, załóżmy, że \(\displaystyle{ T(n,m)}\) zachodzi, tj. \(\displaystyle{ \NWD(a^n, b^m)=1}\) dla pewnych \(\displaystyle{ m,n\in \NN, \ a,b \in \ZZ, \ \NWD(a,b)=1}\).
To oznacza, na mocy wspomnianego twierdzenia, że istnieją takie liczby całkowite \(\displaystyle{ x,y}\), że \(\displaystyle{ x\cdot a^n+y\cdot b^m=1}\).
Wykażemy, że istnieje taka liczba całkowita \(\displaystyle{ p}\), iż \(\displaystyle{ a |\left( x+p\cdot b^m\right)}\).
W tym celu dla ustalenia uwagi załóżmy, że \(\displaystyle{ a>1}\) i popatrzmy na liczby: \(\displaystyle{ x\\x+b^m\\x+2\cdot b^m\\ \ldots\\x+(a-1)b^m}\)
Tych liczb jest \(\displaystyle{ a}\) i żadne dwie nie dają tej samej reszty z dzielenia przez \(\displaystyle{ a}\)
(bo gdyby dawały, to ich różnica dzieliłaby się przez \(\displaystyle{ a}\), co jest wykluczone, wszak skoro \(\displaystyle{ \NWD(a^n, b^m)=1}\), to tym bardziej \(\displaystyle{ \NWD(a,b^m)=1}\)).
W szczególności któraś z nich daje resztę zero z dzielenia przez \(\displaystyle{ a}\), czyli dzieli się przez \(\displaystyle{ a}\).
Natomiast gdyby \(\displaystyle{ a<-1}\), to zamiast tego bierzemy liczby \(\displaystyle{ x, \\x-b^m\\ x-2\cdot b^m\\x+(a+1)b^m}\)
i jest ich \(\displaystyle{ -a}\) o parami różnych resztach z dzielenia przez \(\displaystyle{ -a}\). No a dla \(\displaystyle{ a\in\left\{ -1,1\right\}}\) to twierdzenie w ogóle jest nieciekawe i można wziąć jakiekolwiek \(\displaystyle{ p}\), np. \(\displaystyle{ p=0}\).
Weźmy więc takie \(\displaystyle{ p}\), jak wyżej. Wówczas
liczby \(\displaystyle{ \frac{x+p\cdot b^m}{a}, \ y-p\cdot a^n}\) są całkowite i mamy \(\displaystyle{ \frac{x+p\cdot b^m}{a}\cdot a^{n+1}+\left( y-p\cdot a^n\right)b^m=x\cdot a^n+y\cdot b^m=1}\),
więc korzystając z twierdzenia Gaussa-Bézouta (tym razem w drugą stronę) mamy \(\displaystyle{ \NWD(a^{n+1}, b^m)=1}\).
W całkowicie analogiczny sposób dowodzimy, że \(\displaystyle{ T(n,m)}\) dla liczb całkowitych \(\displaystyle{ n,m\ge 1}\) pociąga \(\displaystyle{ T(n,m+1)}\).
Czyli mamy taki schemat: \(\displaystyle{ \left[T(1,1)\wedge \left( \forall n,m\in \NN^+\right)\left( T(n,m)\Rightarrow T(n+1,m) \right) \wedge \left( \forall n,m\in \NN^+\right)\left( T(n,m)\Rightarrow T(n,m+1) \right) \right]\\\implies (\forall n\in \NN^+)(\forall m\in \NN^+)T(n,m)}\)
a te z zerami (nie wiem, po kiego grzyba zostały dorzucone) oddzielnie sprawdzamy i nie korzystamy z nich w indukcji, ponieważ jeśli np. \(\displaystyle{ n=0}\), to nie możemy z tego, że \(\displaystyle{ \NWD(a^n,b^m)=1}\) wnioskować, że \(\displaystyle{ \NWD(a,b^m)=1}\).
Inaczej: ustalmy \(\displaystyle{ m, n \ge 0}\) i załóżmy, że dla wszystkich par \(\displaystyle{ m', n' \ge 0}\) takich że \(\displaystyle{ m'+n' < m+n}\) jest \(\displaystyle{ \mathrm{NWD}(a^{n'}, b^{m'}) = 1}\). Wykażemy, że \(\displaystyle{ \mathrm{NWD}(a^n, b^m) = 1}\).
Jeśli \(\displaystyle{ n = 0}\) lub \(\displaystyle{ m = 0}\), to teza jest oczywista, przypuśćmy więc, że \(\displaystyle{ m, n \ge 1}\). Ponieważ \(\displaystyle{ a \perp b}\), możemy znaleźć takie \(\displaystyle{ x, y \in \ZZ}\), że \(\displaystyle{ x \cdot a + y \cdot b = 1}\). Z założenia indukcyjnego i z przytoczonego twierdzenia wynika zaś, że istnieją \(\displaystyle{ s, t, u, v \in \ZZ}\), takie że
\(\displaystyle{ s \cdot a^{n-1} + t \cdot b^m = 1 \\
u \cdot a^n + v \cdot b^{m-1}.}\)
Stąd mamy kolejno:
\(\displaystyle{ s \cdot a^n + ta \cdot b^m = a \\
ub \cdot a^n + v \cdot b^m = b \\
1 = x \cdot a + y \cdot b = x \cdot \big( s \cdot a^n + ta \cdot b^m \big) + y \cdot \big( ub \cdot a^n + v \cdot b^m \big) = (xs + yub) \cdot a^n + (xta + yv) \cdot b^m,}\)
a więc pozostaje znów zastosować twierdzenie i koniec.
