NWD - dowód

Podzielność. Reszty z dzielenia. Kongruencje. Systemy pozycyjne. Równania diofantyczne. Liczby pierwsze i względnie pierwsze. NWW i NWD.
bartek118
Gość Specjalny
Gość Specjalny
Posty: 5970
Rejestracja: 28 lut 2010, o 19:45
Płeć: Mężczyzna
Lokalizacja: Toruń
Podziękował: 15 razy
Pomógł: 1251 razy

NWD - dowód

Post autor: bartek118 » 4 sie 2011, o 21:39

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) = \newline = 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?

Mtt-Mmt
Użytkownik
Użytkownik
Posty: 26
Rejestracja: 7 lis 2009, o 17:43
Płeć: Mężczyzna
Pomógł: 4 razy

NWD - dowód

Post autor: Mtt-Mmt » 4 sie 2011, o 22:36

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

bartek118
Gość Specjalny
Gość Specjalny
Posty: 5970
Rejestracja: 28 lut 2010, o 19:45
Płeć: Mężczyzna
Lokalizacja: Toruń
Podziękował: 15 razy
Pomógł: 1251 razy

NWD - dowód

Post autor: bartek118 » 4 sie 2011, o 22:42

Dzięki - przygotowania do egzaminu, no i wychodzą niby to oczywiste rzeczy, a jak coś to jest problem, nie lubię dyskretnej

ODPOWIEDZ