Zadanie. Udowodnić, że \(\displaystyle{ NWD(n^a - 1, n^b - 1) = n^{NWD(a,b)} -1}\)
No więc, moje próby zaczynają się od algorytmu Euklidesa:
\(\displaystyle{ NWD(n^a -1, n^b -1) = NWD(n^b -1, n^a -1 -n^b +1) = \\ = NWD(n^b -1, n^b (n^{a-b}-1)) = NWD(n^b -1, n^{a-b} -1)}\)
\(\displaystyle{ n^{NWD(a,b)} -1 = n^{NWD(b,a-b)} -1}\)
Tak więc, obydwie strony "zachowują się" tak samo, jeśli chodzi o algorytm Euklidesa. Mam jednak problem, aby zapisać to jakoś formalnie, bardzo bym prosił forumowiczów o pomoc. Może jakaś indukcja, lub coś takiego?
NWD - dowód
NWD - dowód
Indukcja na \(\displaystyle{ max\left\{ a,b \right\}}\). Wtedy można uwzględnić dwa przypadki: \(\displaystyle{ a \neq b}\) (masz już wyżej zrobiony krok) oraz oczywisty \(\displaystyle{ a = b}\).
W kroku składa się pięknie po kolei: jeśli \(\displaystyle{ a > b}\), to masz z założenia ind. \(\displaystyle{ NWD\left(n^b-1,n^{a-b}-1\right) = n^{NWD\left(b,a-b\right)}-1}\), a z Euklidesa \(\displaystyle{ n^{NWD\left(b,a-b\right)}-1 = n^{NWD\left(b,a\right)}-1}\) i tyle.
Pozdrawiam,
Mamut
W kroku składa się pięknie po kolei: jeśli \(\displaystyle{ a > b}\), to masz z założenia ind. \(\displaystyle{ NWD\left(n^b-1,n^{a-b}-1\right) = n^{NWD\left(b,a-b\right)}-1}\), a z Euklidesa \(\displaystyle{ n^{NWD\left(b,a-b\right)}-1 = n^{NWD\left(b,a\right)}-1}\) i tyle.
Pozdrawiam,
Mamut