[Teoria liczb] Rozwiązać równanie w liczbach naturalnych

Zadania z kółek matematycznych lub obozów przygotowujących do OM. Problemy z minionych olimpiad i konkursów matematycznych.
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.
Awatar użytkownika
Illidan
Użytkownik
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

Post autor: Illidan » 14 wrz 2007, o 22:43

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
Ostatnio zmieniony 14 wrz 2007, o 22:55 przez Illidan, łącznie zmieniany 1 raz.

Awatar użytkownika
qsiarz
Użytkownik
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

Post autor: qsiarz » 15 wrz 2007, o 01:33

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

Awatar użytkownika
Illidan
Użytkownik
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

Post autor: Illidan » 15 wrz 2007, o 10:39

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.

Awatar użytkownika
Sylwek
Gość Specjalny
Gość Specjalny
Posty: 2711
Rejestracja: 21 maja 2007, o 14:24
Płeć: Mężczyzna
Lokalizacja: Warszawa
Podziękował: 155 razy
Pomógł: 654 razy

[Teoria liczb] Rozwiązać równanie w liczbach naturalnych

Post autor: Sylwek » 23 sie 2008, o 18:56

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ść.

frej

[Teoria liczb] Rozwiązać równanie w liczbach naturalnych

Post autor: frej » 23 sie 2008, o 19:50

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ć?

Awatar użytkownika
Sylwek
Gość Specjalny
Gość Specjalny
Posty: 2711
Rejestracja: 21 maja 2007, o 14:24
Płeć: Mężczyzna
Lokalizacja: Warszawa
Podziękował: 155 razy
Pomógł: 654 razy

[Teoria liczb] Rozwiązać równanie w liczbach naturalnych

Post autor: Sylwek » 23 sie 2008, o 20:02

Po kolei sprawdzam od najmniejszego tzn. np. szuaknymi dzielnikami \(\displaystyle{ (11^{30}-1)}\)\(\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.

frej

[Teoria liczb] Rozwiązać równanie w liczbach naturalnych

Post autor: frej » 23 sie 2008, o 22:33

O, myślałem, że to coś bardziej wymyślnego niż brute-force... Trochę to żmudne niestety...

Awatar użytkownika
Sylwek
Gość Specjalny
Gość Specjalny
Posty: 2711
Rejestracja: 21 maja 2007, o 14:24
Płeć: Mężczyzna
Lokalizacja: Warszawa
Podziękował: 155 razy
Pomógł: 654 razy

[Teoria liczb] Rozwiązać równanie w liczbach naturalnych

Post autor: Sylwek » 23 sie 2008, o 22:43

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

ODPOWIEDZ