Matematyka.pl

Wykaż, że dla liczb naturalnych \(\displaystyle{ a, m, n > 1}\) mamy
\(\displaystyle{ NWD(a^m-1,a^n-1)=a^{NWD(m,n)}-1}\)

Jak to zrobić? Może mi ktoś pomóc?

Skoro \(\displaystyle{ a^k-1}\) dzieli się przez \(\displaystyle{ a^l-1}\) gdzie l jest dowolnym dzielnikiem k, to teza jest oczywista.

Nie jest oczywista - to tylko dowodzi, że prawa strona jest wspólnym dzielnikiem liczb \(\displaystyle{ a^m-1}\) i \(\displaystyle{ a^n-1}\), ale nie że największym.

@max123321, skorzystaj z algorytmu Euklidesa.

Dasio11 pisze: ↑10 lis 2022, o 21:08 Nie jest oczywista (...)

Ależ jest, gdyż \(\displaystyle{ a^k-1}\) nie dzieli się przez \(\displaystyle{ a^l-1}\) jeśli l nie jest dzielnikiem k.

Z całym szacunkiem, podejrzewam że Twoja skłonność do nazywania różnych faktów oczywistymi wynika z niezrozumienia, jak wyglądałby ich pełny i uczciwy dowód. Podany fakt może być sensownym krokiem pośrednim (choć algorytmem Euklidesa jest prościej), ale znów: ani on sam nie jest oczywisty - zatem wymaga dowodu - ani też nie jest oczywiste, w jaki sposób wynika z niego teza. Odnośnie tego ostatniego, z pewnością zauważyłeś że potencjalny większy wspólny dzielnik, którego istnienie chcemy wykluczyć, a priori nie musiałby być postaci \(\displaystyle{ a^l-1}\).

Dasio11 pisze: ↑10 lis 2022, o 23:09 Z całym szacunkiem, podejrzewam że Twoja skłonność do nazywania różnych faktów oczywistymi wynika z niezrozumienia, jak wyglądałby ich pełny i uczciwy dowód.

Jeśli pełnym dowodem nazywać taki, jak wykazanie równości 1+1=2 w ''Principia Mathematica" Russella i Whiteheada, to faktycznie, nawet nie zamierzam sobie go nawet wyobrażać.
Jednakże, obie własności nazywane oczywistymi takimi są, a ich ''uproszczone'' dowody mieszczą się w jednej linijce.
Ponadto, to co napisałem to wskazówki, a nie dowód. Jeśli dobrze liczę, to doktorant max123321 powinien umieć je wykorzystać.

Dasio11 pisze: ↑10 lis 2022, o 23:09 (...) z pewnością zauważyłeś że potencjalny większy wspólny dzielnik, którego istnienie chcemy wykluczyć, a priori nie musiałby być postaci \(\displaystyle{ a^l-1}\).

Niestety, nie zauważyłem. Choć moje wskazówki wyjaśniają dlaczego istnieje dzielnik z tezy, to nie tłumaczą dlaczego jest największym z możliwych.

kerajs pisze: ↑11 lis 2022, o 00:15Jeśli pełnym dowodem nazywać taki, jak wykazanie równości 1+1=2 w ''Principia Mathematica" Russella i Whiteheada, to faktycznie, nawet nie zamierzam sobie go nawet wyobrażać.

Nie da się precyzyjnie określić, kiedy dowód matematyczny jest kompletny (w praktycznym znaczeniu tego słowa) - jest to kwestia pewnego wyczucia, którego nabywa się czytając dobre książki i podręczniki, słuchając wykładów, dyskutując z matematykami. Wyczucia, którego - znów z całym szacunkiem - najwyraźniej Tobie brakuje, jeśli przychodzi Ci do głowy, by proponować za wzorzec książkę Whiteheada i Russela.

kerajs pisze: ↑11 lis 2022, o 00:15Ponadto, to co napisałem to wskazówki, a nie dowód. Jeśli dobrze liczę, to doktorant max123321 powinien umieć je wykorzystać.

Nie mam obiekcji do udzielania wskazówek - postuluję jedynie, by nie nazywać oczywistością czegoś, co ewidentnie oczywiste nie jest.

kerajs pisze: ↑11 lis 2022, o 00:15
Jednakże, obie własności nazywane oczywistymi takimi są, a ich ''uproszczone'' dowody mieszczą się w jednej linijce.

Więc może zamiast pisać cały ten komentarza, napisałbyć tę linijkę

Swoją drogą znana jest anegdota o profesorze, który, poproszony o wyjaśnienie dlaczego przejście w pewnym dowodzie nazwał oczywistym, zadumał sie na pół godziny, po czym stwierdził: "Tak, to jest oczywiste"

a4karo pisze: ↑11 lis 2022, o 11:43

kerajs pisze: ↑11 lis 2022, o 00:15 Jednakże, obie własności nazywane oczywistymi takimi są, a ich ''uproszczone'' dowody mieszczą się w jednej linijce.

Więc może zamiast pisać cały ten komentarza, napisałbyć tę linijkę

Linijka dla \(\displaystyle{ l}\) będącego dzielnikiem \(\displaystyle{ m}\):
\(\displaystyle{ a^m-1=a^{lq}-1=(a^l)^q-1=(a^l-1) \sum_{i=0}^{q}(a^l)^q }\)
Linijka dla \(\displaystyle{ p}\) niebędącego dzielnikiem \(\displaystyle{ m}\):
\(\displaystyle{ a^m-1=\left[ (a^p-1) \sum_{i=1}^{ \lfloor \frac{m}{p} \rfloor }a^{m-ip} \right]+a^{m-\lfloor \frac{m}{p} \rfloor p}-1 }\)

Dasio11 pisze: ↑11 lis 2022, o 11:04Wyczucia, którego - znów z całym szacunkiem - najwyraźniej Tobie brakuje, jeśli przychodzi Ci do głowy, by proponować za wzorzec książkę Whiteheada i Russela.

Rozbawiłeś mnie.