Rozwiązać w liczbach naturalnych
\(\displaystyle{ 2^{m}+3=11^{n}}\)
Rozwiązałem to ale brzydko [; może ktoś zrobi to ładniej
_____
Temat "Fajne zadanie" nie rozjaśnia problemu.
bolo
[Teoria liczb] Rozwiązać równanie w liczbach naturalnych
Regulamin forum
Wszystkie tematy znajdujące się w tym dziale powinny być tagowane tj. posiadać przedrostek postaci [Nierówności], [Planimetria], itp.. Temat może posiadać wiele różnych tagów. Nazwa tematu nie może składać się z samych tagów.
Wszystkie tematy znajdujące się w tym dziale powinny być tagowane tj. posiadać przedrostek postaci [Nierówności], [Planimetria], itp.. Temat może posiadać wiele różnych tagów. Nazwa tematu nie może składać się z samych tagów.
- Illidan
- Użytkownik
- Posty: 14
- Rejestracja: 21 kwie 2006, o 13:01
- Płeć: Mężczyzna
- Lokalizacja: Mikołów
[Teoria liczb] Rozwiązać równanie w liczbach naturalnych
Ostatnio zmieniony 14 wrz 2007, o 22:55 przez Illidan, łącznie zmieniany 1 raz.
- qsiarz
- Użytkownik
- Posty: 202
- Rejestracja: 15 kwie 2006, o 15:32
- Płeć: Mężczyzna
- Lokalizacja: Bytom
- Podziękował: 3 razy
- Pomógł: 18 razy
[Teoria liczb] Rozwiązać równanie w liczbach naturalnych
z tego co pamietam tu sie rozpatrza duzo przystawan roznych modulo i w koncu zwychodzi sprzecznosc, a jedyne rozwiazanie to m=3 n=1. takie zadanie zeby sie pobawic
- Illidan
- Użytkownik
- Posty: 14
- Rejestracja: 21 kwie 2006, o 13:01
- Płeć: Mężczyzna
- Lokalizacja: Mikołów
[Teoria liczb] Rozwiązać równanie w liczbach naturalnych
A ty byłeś na kółku jak to pokazywałem?
Ale może jest ładniejsze rozwiązanie [; na pewno jest jeszcze inne bez modulo ale nie wiem jakie.
Ale może jest ładniejsze rozwiązanie [; na pewno jest jeszcze inne bez modulo ale nie wiem jakie.
- Sylwek
- Użytkownik
- Posty: 2716
- Rejestracja: 21 maja 2007, o 14:24
- Płeć: Mężczyzna
- Lokalizacja: Warszawa
- Podziękował: 160 razy
- Pomógł: 657 razy
[Teoria liczb] Rozwiązać równanie w liczbach naturalnych
Standardowy sposób rozwiązywania takich majstersztyków:
Dla \(\displaystyle{ m\leqslant 3 n qslant 1}\) jest jedno rozwiązanie: \(\displaystyle{ (m,n)=(3,1)}\)
Dla wyższych m,n podstawmy \(\displaystyle{ a=m-3}\) i \(\displaystyle{ b=n-1}\), równanie jest równoważne: \(\displaystyle{ \boxed{8(2^a-1)=11(11^b-1)}}\). Po drodze kilka razy skorzystam z twierdzenia \(\displaystyle{ c|k \iff (a^c-1)|(a^k-1)}\):
(1) Rozpatrując lewą stronę modulo 11 mamy: \(\displaystyle{ 10|a \ \ \ \ 31|(2^{10}-1)|(2^a-1)}\)
(2) Rozpatrując prawą stronę modulo 31: \(\displaystyle{ 30|b \ \ \ \ 19|(11^3-1)|(11^{30}-1)|(11^b-1)}\)
(3) Rozpatrując lewą stronę modulo 19: \(\displaystyle{ 18|a \ \ \ \ 73|(2^{18}-1)|(2^a-1)}\)
(4) Rozpatrując prawą stronę modulo 73: \(\displaystyle{ 72|b \ \ \ \ 16|(11^4-1)|(11^{72}-1)|(11^b-1)}\) - zatem prawa strona jest podzielna przez 16, a lewa nie - sprzeczność.
Dla \(\displaystyle{ m\leqslant 3 n qslant 1}\) jest jedno rozwiązanie: \(\displaystyle{ (m,n)=(3,1)}\)
Dla wyższych m,n podstawmy \(\displaystyle{ a=m-3}\) i \(\displaystyle{ b=n-1}\), równanie jest równoważne: \(\displaystyle{ \boxed{8(2^a-1)=11(11^b-1)}}\). Po drodze kilka razy skorzystam z twierdzenia \(\displaystyle{ c|k \iff (a^c-1)|(a^k-1)}\):
(1) Rozpatrując lewą stronę modulo 11 mamy: \(\displaystyle{ 10|a \ \ \ \ 31|(2^{10}-1)|(2^a-1)}\)
(2) Rozpatrując prawą stronę modulo 31: \(\displaystyle{ 30|b \ \ \ \ 19|(11^3-1)|(11^{30}-1)|(11^b-1)}\)
(3) Rozpatrując lewą stronę modulo 19: \(\displaystyle{ 18|a \ \ \ \ 73|(2^{18}-1)|(2^a-1)}\)
(4) Rozpatrując prawą stronę modulo 73: \(\displaystyle{ 72|b \ \ \ \ 16|(11^4-1)|(11^{72}-1)|(11^b-1)}\) - zatem prawa strona jest podzielna przez 16, a lewa nie - sprzeczność.
[Teoria liczb] Rozwiązać równanie w liczbach naturalnych
Chciałem się zapytać w jaki sposób znajdujesz te dzielniki
\(\displaystyle{ 30|b \ \ \ \ 19|(11^3-1)|(11^{30}-1)|(11^b-1)}\)
czy
\(\displaystyle{ 18|a \ \ \ \ 73|(2^{18}-1)|(2^a-1)}\)
?
Chodzi oczywiście o \(\displaystyle{ 19}\) i \(\displaystyle{ 73}\) ? Domyślam się, że dobrze jest gdy są pierwsze, bo wtedy łatwo można zastosować MTF, ale jak je wybrać?
\(\displaystyle{ 30|b \ \ \ \ 19|(11^3-1)|(11^{30}-1)|(11^b-1)}\)
czy
\(\displaystyle{ 18|a \ \ \ \ 73|(2^{18}-1)|(2^a-1)}\)
?
Chodzi oczywiście o \(\displaystyle{ 19}\) i \(\displaystyle{ 73}\) ? Domyślam się, że dobrze jest gdy są pierwsze, bo wtedy łatwo można zastosować MTF, ale jak je wybrać?
- Sylwek
- Użytkownik
- Posty: 2716
- Rejestracja: 21 maja 2007, o 14:24
- Płeć: Mężczyzna
- Lokalizacja: Warszawa
- Podziękował: 160 razy
- Pomógł: 657 razy
[Teoria liczb] Rozwiązać równanie w liczbach naturalnych
Po kolei sprawdzam od najmniejszego tzn. np. szuaknymi dzielnikami \(\displaystyle{ (11^{30}-1)}\) są \(\displaystyle{ 11^2-1, \ 11^3-1, \ 11^5-1}\) itp. - po kolei rozpatruję dzielniki każdej z tych potęg, to w pewnym sensie przypomina metodę prób i błędów - przy robieniu tego przykładu wypisałem sobie z 10 takich podzielności, a 4 okazały się bezpośrednio przydatne.
[Teoria liczb] Rozwiązać równanie w liczbach naturalnych
O, myślałem, że to coś bardziej wymyślnego niż brute-force... Trochę to żmudne niestety...
- Sylwek
- Użytkownik
- Posty: 2716
- Rejestracja: 21 maja 2007, o 14:24
- Płeć: Mężczyzna
- Lokalizacja: Warszawa
- Podziękował: 160 razy
- Pomógł: 657 razy
[Teoria liczb] Rozwiązać równanie w liczbach naturalnych
Rozwiązanie tego przykładu nie zajęło mi dłużej niż 20 minut, przy czym dużo czasu faktoryzacja (rozkład na czynniki) niektórych liczb . Pewnie jest wiele różnych dróg rozwiązania problemu i dla innych modulo też dojdziemy do sprzeczności - mi się udało dla tych - możesz spróbować dla treningu dla innych