Nevíte-li si rady s jakýmkoliv matematickým problémem, toto místo je pro vás jako dělané.
Nástěnka
❗22. 8. 2021 (L) Přecházíme zpět na doménu forum.matweb.cz!
❗04.11.2016 (Jel.) Čtete, prosím, před vložení dotazu, děkuji!
❗23.10.2013 (Jel.) Zkuste před zadáním dotazu použít některý z online-nástrojů, konzultovat použití můžete v sekci CAS.
Nejste přihlášen(a). Přihlásit
Stránky: 1 2
Zdravím,
tuhle úlohu jsem řešil asi před pěti lety a dokazování mi trvalo asi tři týdny. Důkaz jsem ale z větší části zapomněl a nepodařilo se mi ho dohledat.
Tak se obracím na profesionály, jestli to nejde nějak jednodušeji...:-) Zadání:
Najděte (a dokažte přitom, že jich je konečně mnoho) všechny dvojice přirozených čísel [mathjax](k,n)[/mathjax] pro které platí
[mathjax]|2^{k}-3^{n}|=1[/mathjax]
Offline
Ahoj,
taky jsem kdysi viděl řešení a taky jsem ho zapomněl. :-)
Offline
↑ osman:
Slyšel jsem, že je pouze jedna dvojice [3;2], 2^3 - 3^2 =8-9=-1
Jiné prý nejsou, ale dokázat to neumím. Není to jednoduché.
Offline
↑ Richard Tuček: - ano, pro [mathjax]k>1,n>1[/mathjax] je tomu tak.
Ale zjistil jsem, že jsem jako radio Jerevan.
Řešení této úlohy je důsledek Catalanovy domněnky https://en.m.wikipedia.org/wiki/Catalan%27s_conjecture dokázané v roce 2002 Predem Mihăilescu.
Pravda je taková, že jsem Mihăilescuovu větu použil k důkazu (který jsem konečně našel) konečnosti množiny
[mathjax]M=\{n\in \mathbb{N}\setminus \{1\};\forall p,q\in \mathbb{P}:p\le n\wedge q\le n\wedge p<>q\Rightarrow n(mod p)<>n(mod q)\}[/mathjax]
Laskavému publiku se tímto omlouvám za svou sklerózu a kladu otázku: Jak vypadá monožina [mathjax]M[/mathjax]?
(Myslím, že lidský popis množiny M by mohl znít: Když číslo [mathjax]n[/mathjax] vydělíte postupně všemi prvočísly, ktetrá jsou menší nebo rovna [mathjax]n[/mathjax], dostanete pokaždé jiný zbytek. Kolik takových čísel [mathjax]n[/mathjax] je a která to jsou?)
Offline
↑ osman:
Podle mě jsem viděl jednodušší důkaz, ale už nevím.
Takže je povoleno při hledání tvaru množiny M použít Mihăilescuovu větu?
Offline
↑ check_drummer:
Povoleno je vše, co je korektní a vede k cíli:-)
Offline
↑ osman:
Spíš mi šlo o to, která tvrzení lze použít bez důkazu. Protože kdybych si někde na internetu našel, jaké prvky patří do M a napsal to sem, tak by to asi nebylo uznatelné.
Offline
Nechcete na to někdo napsat skript, aby bylo vidět prvních pár čísel množiny M? Třeba mezi 1 a 1000? :-)
Offline
↑ check_drummer:
"Spíš mi šlo o to, která tvrzení lze použít bez důkazu. Protože kdybych si někde na internetu našel, jaké prvky patří do M a napsal to sem, tak by to asi nebylo uznatelné."
Myslel jsem tím, že k podpoře důkazu lze použít již dokázané věty kromě té, jejíž výsledkem je přímo množina M:-)
Pozn.:
Úlohu jsem řešil na jednom fóru. Když jsem se zasekl na Catalinově domněnce, kdosi mě upozornil, že je to dávno dokázané...
Co se týče jednoduchosti důkazu, jeden účastník to dokazoval ještě divočeji pomocí Mersennových prvočísel a posloupnosti intervalů:-)
Offline
↑ check_drummer:
Z definice množiny M mi vypadla podmínka [mathjax]p,q\le n[/mathjax]. Opravil jsem do definice M i do jejího slovního popisu.
Offline
↑ osman:
A nemáš teda příklad několik prvků množiny M? - řekněme mezi čísly 1 a 1000? Podle mě není žádná velká rada když to sem napíšeš, každý kdo není líný (já jsem) si na to může snadno napsat program.... A podvod to určitě není...
Offline
↑ check_drummer:
2,3,4,5,8,9
Zkus najít sedmý prvek
Offline
↑ osman:
Pozdravujem,
Kukni si aj toto
https://www.google.fr/url?sa=t&rct= … EA4auOa8P4
Offline
osman napsal(a):
↑ check_drummer:
2,3,4,5,8,9
Zkus najít sedmý prvek
Do 20 se nadaří... Skoro to vypadá, že už další není?....
Offline
↑ check_drummer:
Jenom to dokázat...:-(
Offline
↑ vanok:
Pěkné. Je to tak jednoduché, že je to až nezajímavé. :-) Ale je na tom krásně vidět že i pomocí jednoduchých úvah lze získat netriviální tvrzení.
Offline
↑ osman:
Že by stačilo uvažovat jen taková prvočísla, z nichž jedno z nich je 2 nebo 3?
Offline
Já si to ale možná pletu s jinou úlohou - kdy rozdíl nějakých dvou (alespoň druhých) mocnin je 2. Jedno řešení je 27 a 25. A skoro mám pocit že jiná už nejsou...
Offline
↑ check_drummer:
Myslím, že napřed je třeba ukázat, že prvky množiny M musí být pouze ve tvaru [mathjax]n=2^{k}[/mathjax] nebo [mathjax]n=2^{k}+1[/mathjax], a potom eliminovat [mathjax]k[/mathjax], pro která to nemůže platit.
Mihăilescuovu větu jsem použil pro eliminaci čísel [mathjax]n=2^{k}+1[/mathjax], která jsou dělitelná třemi.
Offline
1) Pro prvočísla p<q do množiny M nepadnou čísla n.p.q až n.p.q+p-1 (včetně) pro libovllné n přirozené, tedy jde o za sebou jdoucích p čísel. Dále se budeme zabývat případy kdy p=2 nebo p=3.
2) Tedy mám-li sudé číslo x, které není mocnina dvojky (tedy v jeho rozkladu je další prvočíslo kromě 2), tak do M nepadnou čísla x,x+1.
3) Podobně mám-li liché číslo >1 (které není mocnina), pak do M nepadnou čísla x,x+1,x+2.
4) Tedy problémové jsou mocniny dvojky - pokud je pro takové číslo x nějaký násobek čísla 3 (který není mocninou 3) o 1 menší než x, tak tedy x-1,x,x+1 nepadne do M. A podle věty, kterou smíme použít víme, že až na x=4 nebude nikdy x-1 mocninou 3.
5) Zbývá vyřešit případ, kdy x je mocnina 2ky a kdy x+1 je násobek čísla 3. Opět nemůže být x+1 mocnina 3 (kromě x=2 a x=8), a tedy není z M. Potom tedy je x-2 násobek 2 (ale nikoli 4) a 3. Pokud by x-2 mělo jiné prvočíselné násobky než 2,3, tak z 1) plyne, že ani x-2,x-1,x není z M. Ovšem pokud je x-2 jen násobek 2 a 3, pak je x-2=2.3^c, x=2^d a tedy po vydělení 2 jsou 3^c,2^{d-1} sousední čísla, což může nastat jen pro c=1 a d=3, tj. x=8, a víme že 8 je z M.
Offline
↑ osman:
Zrovna jsem to začal sepisovat, asi jdu na to podobně jako ty.
Offline
A pokud by platilo toto:
↑ check_drummer:
... alespoň pro lichá provočísla - nebo jen pro konečně mnoho čísel, která by byla známá, tak by to bylo ještě jednodušší, stačilo by pro lichou mocninu x prvočísla uvážit jen číslo x-2.
Offline
A pokud by platilo toto: ↑ check_drummer: ... alespoň pro lichá provočísla - nebo jen pro konečně mnoho čísel, která by byla známá, tak by to bylo ještě jednodušší, stačilo by pro lichou mocninu x prvočísla uvážit jen číslo x-2.
Šlo by to trochu rozvést? Moc jsem nepochopil, oč přesně jde:-)
Offline
↑ check_drummer:
Ještě k důkazu - dělal jsem to podobně, rozdělil jsem si to podle různých mocnin čísla 2.
Už víme, že prvkem množiny M může být pouze číslo ve tvaru [mathjax]2^{k}[/mathjax] nebo [mathjax]2^{k}+1[/mathjax].
--------------------------
Platí [mathjax]2^{4k}mod3=2^{4k}mod5=1[/mathjax]
tedy [mathjax](2^{4k}+1)mod3=(2^{4k}+1)mod5=2[/mathjax]
a proto taky [mathjax]2^{4k+1}mod3=2^{4k+1}mod5=2[/mathjax]
Číslo [mathjax]2^{4k+1}+1[/mathjax] musí být mocninou prvočísla a současně dělitelné 3, takže to musí být mocnina tří. To ale podle M. věty není možné.
Tím máme vyřízené první dvě mocniny.
--------------------------
Obdobnou úvahu použijeme i pro čísla [mathjax]2^{4k+2},2^{4k+2}+1,2^{4k+3},2^{4k+3}+1[/mathjax]
protože [mathjax]2^{4k+2}mod3=2^{4k+2}mod7=1[/mathjax]
A důkaz je hotov. Tedy doufám, že to není celé blbě:-)
Offline
Stránky: 1 2