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

[Illidan]

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

[qsiarz]

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]

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.

[Sylwek]

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]

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

[Sylwek]

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.

[frej]

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

[Sylwek]

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