NWD - dowód
: 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) = \\ = 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?
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?