Witam,
Mam pokazać, że:
\(\displaystyle{ \gcd(n^a-1, n^b-1) = n^{\gcd(a,b)} - 1}\).
Jedyne co potrafię pokazać, to to że \(\displaystyle{ n^{\gcd(a,b)} - 1}\) jest rzeczywiście dzielnikiem tych dwóch liczb oraz, że jest największym dzielnikiem, ale dokładnie tej postaci, tzn postaci: \(\displaystyle{ a^k-1\ \ \ \ \ k> 0}\).
Nie wiem jak pokazać, że większego dzielnika nie ma lub alternatywnie, że każdy dzielnik wspólny tych liczb musi mieć taką postać.
Jakaś wskazówka ?
Pokazać, równość z nwd
-
Zahion
- Moderator
- Posty: 2095
- Rejestracja: 9 gru 2012, o 19:46
- Płeć: Mężczyzna
- Lokalizacja: Warszawa, mazowieckie
- Podziękował: 139 razy
- Pomógł: 504 razy
Pokazać, równość z nwd
Ja bym spróbował tak :
Niech \(\displaystyle{ NWD(a,b)=d}\). Dla pewnych liczb \(\displaystyle{ x, y}\) takich, że \(\displaystyle{ NWD(x,y)=1}\) mamy równość \(\displaystyle{ a=dx, b=dy}\). Stąd mamy, że \(\displaystyle{ n^{a}-1=n^{dx}-1=(n^{d}-1)(n^{dx-d}+...+1)}\) i \(\displaystyle{ n^{b}-1=n^{dy}-1=(n^{d}-1)(n^{dy-d}+...+1)}\). Zauważ, że \(\displaystyle{ n^{d}-1=n^{nwd(a,b)}-1}\) stąd wystarczy wykazać, że \(\displaystyle{ NWD(n^{dy-d}+...+1,n^{dx-d}+...+1)=1}\) przy założeniu, że \(\displaystyle{ NWD(x,y)=1}\)
Niech \(\displaystyle{ NWD(a,b)=d}\). Dla pewnych liczb \(\displaystyle{ x, y}\) takich, że \(\displaystyle{ NWD(x,y)=1}\) mamy równość \(\displaystyle{ a=dx, b=dy}\). Stąd mamy, że \(\displaystyle{ n^{a}-1=n^{dx}-1=(n^{d}-1)(n^{dx-d}+...+1)}\) i \(\displaystyle{ n^{b}-1=n^{dy}-1=(n^{d}-1)(n^{dy-d}+...+1)}\). Zauważ, że \(\displaystyle{ n^{d}-1=n^{nwd(a,b)}-1}\) stąd wystarczy wykazać, że \(\displaystyle{ NWD(n^{dy-d}+...+1,n^{dx-d}+...+1)=1}\) przy założeniu, że \(\displaystyle{ NWD(x,y)=1}\)
-
Zahion
- Moderator
- Posty: 2095
- Rejestracja: 9 gru 2012, o 19:46
- Płeć: Mężczyzna
- Lokalizacja: Warszawa, mazowieckie
- Podziękował: 139 razy
- Pomógł: 504 razy
Pokazać, równość z nwd
Przy danych oznaczeniach zadanie sprowadza się do postaci :
Wyznacz \(\displaystyle{ NWD((n^{d}-1)(n^{dx-d}+...+1),(n^{d}-1)(n^{dy-d}+...+1))}\). Tyle, że Ty masz postawiony fakt, czyli po prostu masz udowodnić, że \(\displaystyle{ NWD((n^{d}-1)(n^{dx-d}+...+1),(n^{d}-1)(n^{dy-d}+...+1))=n^{nwd(a,b)}-1=n^{d}-1}\). Oczywiście jeśli wykażesz, że liczby \(\displaystyle{ n^{dx-d}+...+1}\) i \(\displaystyle{ n^{dy-d}+...+1}\) są względnie pierwsze to zakończy to dowód, bo wtedy jedynym dzielnikiem tych liczb ( jedynym i największym ) będzie właśnie \(\displaystyle{ n^{d}-1}\). Mam nadzieje, że nigdzie blefa tutaj nie puszczam .
Wyznacz \(\displaystyle{ NWD((n^{d}-1)(n^{dx-d}+...+1),(n^{d}-1)(n^{dy-d}+...+1))}\). Tyle, że Ty masz postawiony fakt, czyli po prostu masz udowodnić, że \(\displaystyle{ NWD((n^{d}-1)(n^{dx-d}+...+1),(n^{d}-1)(n^{dy-d}+...+1))=n^{nwd(a,b)}-1=n^{d}-1}\). Oczywiście jeśli wykażesz, że liczby \(\displaystyle{ n^{dx-d}+...+1}\) i \(\displaystyle{ n^{dy-d}+...+1}\) są względnie pierwsze to zakończy to dowód, bo wtedy jedynym dzielnikiem tych liczb ( jedynym i największym ) będzie właśnie \(\displaystyle{ n^{d}-1}\). Mam nadzieje, że nigdzie blefa tutaj nie puszczam .
-
Hydra147
- Użytkownik
- Posty: 268
- Rejestracja: 31 mar 2013, o 20:23
- Płeć: Mężczyzna
- Lokalizacja: Polska
- Podziękował: 1 raz
- Pomógł: 82 razy
Pokazać, równość z nwd
To stwierdzenie jest nieprawdziwe. Więcej, można pokazać (za pomocą algorytmu Euklidesa), że największy wspólny dzielnik tych liczb jest równy \(\displaystyle{ n^{d}+1}\).Oczywiście jeśli wykażesz, że liczby \(\displaystyle{ n^{dx-d}+...+1}\) i \(\displaystyle{ n^{dy-d}+...+1}\) są względnie pierwsze to zakończy to dowód.
Co do zadania. Tu również z pomocą przychodzi nam algorytm (oraz lemat) Euklidesa. Pokażę jego działanie na przykładzie \(\displaystyle{ (a,b)=(8,6)}\):
\(\displaystyle{ NWD(n^8-1, n^6-1)=NWD(n^8-n^6,n^6-1)=NWD(n^2-1,n^6-1)=NWD(n^2-1,n^6-n^4)=NWD(n^2-1,n^4-1)=NWD(n^2-1,n^4-n^2)=NWD(n^2-1,n^2-1)=n^2-1= n^{NWD(8,6)}-1}\).
-
Zahion
- Moderator
- Posty: 2095
- Rejestracja: 9 gru 2012, o 19:46
- Płeć: Mężczyzna
- Lokalizacja: Warszawa, mazowieckie
- Podziękował: 139 razy
- Pomógł: 504 razy
Pokazać, równość z nwd
Czyli dla \(\displaystyle{ x=3, y=2}\) największym wspólnym dzielnikiem liczb \(\displaystyle{ n^{2d}+n^{d}+1, n^{d}+1}\) jest \(\displaystyle{ n^{d}+1}\) ? Nietrudno wykazać, że te liczby nie mają wspólnego dzielnika\(\displaystyle{ k| (n^{2d}+n^{d}+1)-(n^{d}+1)=n^{2d} \Leftrightarrow k|n \Leftrightarrow k|1}\)Hydra pisze:To stwierdzenie jest nieprawdziwe. Więcej, można pokazać (za pomocą algorytmu Euklidesa), że największy wspólny dzielnik tych liczb jest równy n^{d}+1.
Ostatnio zmieniony 25 sie 2014, o 12:27 przez Zahion, łącznie zmieniany 1 raz.
-
matinf
- Użytkownik
- Posty: 1922
- Rejestracja: 26 mar 2012, o 18:52
- Płeć: Mężczyzna
- Lokalizacja: Warszawa
- Podziękował: 695 razy
- Pomógł: 4 razy
Pokazać, równość z nwd
Jak to ?To stwierdzenie jest nieprawdziwe.
@Hydra147, fajny masz ten pomysł s algorytmem.
Czyli zadanie rozwiązane, ale chciałbym, zobaczyć czy moje rozumowanie uda się dociągnąć.
-
Hydra147
- Użytkownik
- Posty: 268
- Rejestracja: 31 mar 2013, o 20:23
- Płeć: Mężczyzna
- Lokalizacja: Polska
- Podziękował: 1 raz
- Pomógł: 82 razy
Pokazać, równość z nwd
Przepraszam, pomyłka . Tak, stwierdzenie Zahiona jest prawdziwe. Podstawmy sobie dla wygody \(\displaystyle{ t= n^{d}}\) i mamy (algorytm again ):
\(\displaystyle{ NWD(t^{x-1}+...+1,t^{y-1}+...+1)=...}\) Działa to analogowo jak w moim rozumowaniu. W pierwszej z tych sum jest \(\displaystyle{ x}\) składników, w drugiej \(\displaystyle{ y}\). Jeżeli gdzieś jest więcej to odejmujemy od niej sumę z mniejszą ilością składników i całość dzielimy przez odpowiednią potęgę \(\displaystyle{ t}\), a że \(\displaystyle{ (x,y)}\) są względnie pierwsze to dojdziemy do jedynki.
\(\displaystyle{ NWD(t^{x-1}+...+1,t^{y-1}+...+1)=...}\) Działa to analogowo jak w moim rozumowaniu. W pierwszej z tych sum jest \(\displaystyle{ x}\) składników, w drugiej \(\displaystyle{ y}\). Jeżeli gdzieś jest więcej to odejmujemy od niej sumę z mniejszą ilością składników i całość dzielimy przez odpowiednią potęgę \(\displaystyle{ t}\), a że \(\displaystyle{ (x,y)}\) są względnie pierwsze to dojdziemy do jedynki.
-
matinf
- Użytkownik
- Posty: 1922
- Rejestracja: 26 mar 2012, o 18:52
- Płeć: Mężczyzna
- Lokalizacja: Warszawa
- Podziękował: 695 razy
- Pomógł: 4 razy
Pokazać, równość z nwd
Trochę ten algorytm uproszczasz. Przede wszystkim:
Możemy stosować algorytm z odejmowaniem - w każdym kroku odejmować mniejszą od większej. Ale jakim cudem dzielić przez odpowiednią potęgę \(\displaystyle{ t}\) ? Ponadto wcale nie widać, żeby względna pierwszość tutaj pomagała w "zejściu do jedynki".
Możemy stosować algorytm z odejmowaniem - w każdym kroku odejmować mniejszą od większej. Ale jakim cudem dzielić przez odpowiednią potęgę \(\displaystyle{ t}\) ? Ponadto wcale nie widać, żeby względna pierwszość tutaj pomagała w "zejściu do jedynki".
-
Zahion
- Moderator
- Posty: 2095
- Rejestracja: 9 gru 2012, o 19:46
- Płeć: Mężczyzna
- Lokalizacja: Warszawa, mazowieckie
- Podziękował: 139 razy
- Pomógł: 504 razy
Pokazać, równość z nwd
Ja bym zastosował bardziej algorytm typu ( pokaże na przykładzie ). Od razu założenie \(\displaystyle{ x > y}\) będzie przydatne.
Dla \(\displaystyle{ x = 11, y =5}\) mamy, że \(\displaystyle{ a = t^{10} + t^{9} + ... + 1}\) i \(\displaystyle{ b = t^{4} + ... + 1}\). Zakładamy, że \(\displaystyle{ NWD(a,b)=p, p>1}\) Od większej liczby grupujemy wyrazy w ten sposób, ażeby uzbierać jak najwięcej wyrazów podzielnych przez \(\displaystyle{ b}\). tj. \(\displaystyle{ a = t^{10} + t^{9} + t^{4}(t^{4}+t^{3}+...+1)+(t^{4}+...+1)=t^{10}+t^{9} + t^{4}b+b}\). Stąd oczywiście \(\displaystyle{ p|t^{10}+t^{9}=t^{9}(t+1)}\). Nietrudno z góry wykazać, że nie może zachodzić podzielność \(\displaystyle{ p|t}\). Otrzymaliśmy w ten sposób liczbę \(\displaystyle{ c = t+1}\) ( która musi być podzielna przez \(\displaystyle{ p}\) i dalej z liczb \(\displaystyle{ a, b}\) wybieramy liczbę o mniejszej ilości wyrazów, tj. liczbę \(\displaystyle{ b}\). Rozpatrujemy więc liczby \(\displaystyle{ b,c}\). Kontynuując mamy, że \(\displaystyle{ b = t^{4}+t^{3}+t^{2}+t+1=t^{4}+t^{2}(t+1)+(t+1)=t^{4}+t^{2}c+c}\). Koniec końców po skończonej liczbie takich przejść dochodzimy do momentu w którym \(\displaystyle{ p | t}\) co daje sprzeczność i mówi nam, że \(\displaystyle{ p = 1}\). Do czego nam konkretniej to, że liczby są względnie pierwsze, a no na pewno do tego, że ilość wyrazów to kolejno \(\displaystyle{ x, y}\), które są względnie pierwsze i nie pozwalają się dzięki temu zgrupować i dowodzą tego, że na końcu otrzymamy jeden wyraz, którym będzie \(\displaystyle{ t^{n}}\) dla pewnego \(\displaystyle{ n}\).
Add. Trzeba tutaj jeszcze zaznaczyć, że korzystamy z tego \(\displaystyle{ NWD(a^{x}+a^{x-1}+...+1, a^{y})=1}\), gdzie \(\displaystyle{ a,x,y \in N}\) i \(\displaystyle{ x \ge 1}\), bo w przeciwnym wypadku stwierdzenie nie byłoby prawdziwe.
Dla \(\displaystyle{ x = 11, y =5}\) mamy, że \(\displaystyle{ a = t^{10} + t^{9} + ... + 1}\) i \(\displaystyle{ b = t^{4} + ... + 1}\). Zakładamy, że \(\displaystyle{ NWD(a,b)=p, p>1}\) Od większej liczby grupujemy wyrazy w ten sposób, ażeby uzbierać jak najwięcej wyrazów podzielnych przez \(\displaystyle{ b}\). tj. \(\displaystyle{ a = t^{10} + t^{9} + t^{4}(t^{4}+t^{3}+...+1)+(t^{4}+...+1)=t^{10}+t^{9} + t^{4}b+b}\). Stąd oczywiście \(\displaystyle{ p|t^{10}+t^{9}=t^{9}(t+1)}\). Nietrudno z góry wykazać, że nie może zachodzić podzielność \(\displaystyle{ p|t}\). Otrzymaliśmy w ten sposób liczbę \(\displaystyle{ c = t+1}\) ( która musi być podzielna przez \(\displaystyle{ p}\) i dalej z liczb \(\displaystyle{ a, b}\) wybieramy liczbę o mniejszej ilości wyrazów, tj. liczbę \(\displaystyle{ b}\). Rozpatrujemy więc liczby \(\displaystyle{ b,c}\). Kontynuując mamy, że \(\displaystyle{ b = t^{4}+t^{3}+t^{2}+t+1=t^{4}+t^{2}(t+1)+(t+1)=t^{4}+t^{2}c+c}\). Koniec końców po skończonej liczbie takich przejść dochodzimy do momentu w którym \(\displaystyle{ p | t}\) co daje sprzeczność i mówi nam, że \(\displaystyle{ p = 1}\). Do czego nam konkretniej to, że liczby są względnie pierwsze, a no na pewno do tego, że ilość wyrazów to kolejno \(\displaystyle{ x, y}\), które są względnie pierwsze i nie pozwalają się dzięki temu zgrupować i dowodzą tego, że na końcu otrzymamy jeden wyraz, którym będzie \(\displaystyle{ t^{n}}\) dla pewnego \(\displaystyle{ n}\).
Add. Trzeba tutaj jeszcze zaznaczyć, że korzystamy z tego \(\displaystyle{ NWD(a^{x}+a^{x-1}+...+1, a^{y})=1}\), gdzie \(\displaystyle{ a,x,y \in N}\) i \(\displaystyle{ x \ge 1}\), bo w przeciwnym wypadku stwierdzenie
:
-
Hydra147
- Użytkownik
- Posty: 268
- Rejestracja: 31 mar 2013, o 20:23
- Płeć: Mężczyzna
- Lokalizacja: Polska
- Podziękował: 1 raz
- Pomógł: 82 razy
Pokazać, równość z nwd
A mogę dzielić przez odpowiednią potęgę \(\displaystyle{ t}\) na mocy takiego oto faktu:
Jeżeli \(\displaystyle{ (a,c)=1}\) oraz \(\displaystyle{ c|ab}\), to \(\displaystyle{ c|b}\).
Co do tego "zejścia do jedynki" to zauważ, że na początku pierwsza suma ma \(\displaystyle{ x}\) składników, druga \(\displaystyle{ y}\). Jeżeli \(\displaystyle{ x>y}\), to odejmujemy drugą sumę od pierwszej i pierwsza ma teraz \(\displaystyle{ x-y}\) składników itd. wykonujemy algorytm Euklidesa w dokładnie taki sam sposób, w jaki wykonywalibyśmy go na liczbach \(\displaystyle{ x}\) i \(\displaystyle{ y}\). W pewnym momencie dojdziemy do momentu \(\displaystyle{ ...=NWD(t^n-1,t^m)=1}\) co zakończy dowód. I nic tutaj nie upraszczam tylko staram się przedstawić Ci to jak najbardziej przejrzyście (tak, wiem- wyrażanie moich myśli nie wychodzi mi najlepiej).
Zahion mnie ubiegł ale i tak wrzucę posta. On z kolei również (poniękąd) stosuje algorytm Euklidesa, tylko zamiast odejmować za każdym razem od razu bierze reszty z dzielenia (czyli zamiast przekształcać \(\displaystyle{ (6,28)=(6,22)=(6,16)=(6,10)=(6,4)}\) od razu przechodzi z \(\displaystyle{ (6,28)}\) do \(\displaystyle{ (6,4)=(2,4)=2}\)
Jeżeli \(\displaystyle{ (a,c)=1}\) oraz \(\displaystyle{ c|ab}\), to \(\displaystyle{ c|b}\).
Co do tego "zejścia do jedynki" to zauważ, że na początku pierwsza suma ma \(\displaystyle{ x}\) składników, druga \(\displaystyle{ y}\). Jeżeli \(\displaystyle{ x>y}\), to odejmujemy drugą sumę od pierwszej i pierwsza ma teraz \(\displaystyle{ x-y}\) składników itd. wykonujemy algorytm Euklidesa w dokładnie taki sam sposób, w jaki wykonywalibyśmy go na liczbach \(\displaystyle{ x}\) i \(\displaystyle{ y}\). W pewnym momencie dojdziemy do momentu \(\displaystyle{ ...=NWD(t^n-1,t^m)=1}\) co zakończy dowód. I nic tutaj nie upraszczam tylko staram się przedstawić Ci to jak najbardziej przejrzyście (tak, wiem- wyrażanie moich myśli nie wychodzi mi najlepiej).
Zahion mnie ubiegł ale i tak wrzucę posta. On z kolei również (poniękąd) stosuje algorytm Euklidesa, tylko zamiast odejmować za każdym razem od razu bierze reszty z dzielenia (czyli zamiast przekształcać \(\displaystyle{ (6,28)=(6,22)=(6,16)=(6,10)=(6,4)}\) od razu przechodzi z \(\displaystyle{ (6,28)}\) do \(\displaystyle{ (6,4)=(2,4)=2}\)