Teoria liczb, zadanie nr 1404
ostatnie wiadomo艣ci | regulamin | latex
| Autor | Zadanie / Rozwi膮zanie |
polkiuyt post贸w: 34 |  2013-06-06 22:44:52Poka偶, 偶e je艣li Fn jest n-t膮 z kolei liczb膮 Fermata, to (Fn,Fm)= F(n,m) Wiadomo艣膰 by艂a modyfikowana 2013-06-09 08:29:09 przez polkiuyt |
tumor post贸w: 8070 | 2013-06-10 21:03:41 Tre艣膰 zadania jest sprzeczna z tre艣ci膮 zadania http://www.forum.math.edu.pl/temat,studia,1403,0 Przy tym nieprawda jest w tym zadaniu. ;) Podpowiem - tu powinny by膰 wyrazy ci膮gu Fibonacciego, natomiast w 1403 rzecz dotyczy liczb Fermata. A zatem niech $F_n$ b臋dzie n-tym wyrazem ci膮gu Fibonacciego. Zauwa偶my, 偶e $F_{m+n}=F_0F_{m+n-1}+F_1F_{m+n}= F_0F_{m+n-1}+F_1(F_{m+n-2}+F_{m+n-1})= F_1F_{m+n-2}+F_2F_{m+n-1}= F_2F_{m+n-3}+F_3F_{m+n-2}= ... =F_mF_{n-1}+F_{m+1}F_n$ St膮d dostajemy od razu, 偶e $F_{m+m}=F_mF_{m-1}+F_{m+1}F_m$, czyli $F_n|F_{2n}$ Podobnie $F_{m+2m}=F_mF_{2m-1}+F_{m+1}F_{2m}$ i indukcyjnie $F_{m+km}=F_mF_{km-1}+F_{m+1}F_{km}$, czyli $F_n|F_{ln}$ dla $l\in N$ czyli $(F_m,F_n)\ge F_{(n,m)}$ Ponadto dysponujemy prostszym faktem, 偶e $(F_n, F_{n+1})=1$ (Dow贸d jest prosty, gdyby mia艂y wsp贸lny dzielnik $p$, to tak偶e $F_{n-1}$ by艂oby podzielne przez $p$, i tak kolejno a偶 do $p|1$) Przyjmijmy $m>n$, wtedy $m=x_1n+r_1$, gdzie $0\le r_1<n$, czyli typowe dzia艂anie z algorytmu Euklidesa. $(F_m,F_n)=(F_{x_1n+r_1},F_n)=(F_{x_1n-1}F_{r_1}+F_{x_1n}F_{r_1+1},F_n)=(F_{x_1n-1}F_{r_1},F_n)$ (Co wynika z do艣膰 elementarnych w艂asno艣ci NWD, kt贸rych nie dowodz臋). Dalej wiemy, 偶e $(F_{x_1n-1},F_{x_1n})=1$, wi臋c tym bardziej $(F_{x_1n-1},F_n)=1$, skoro tak, to $(F_{x_1n-1}F_{r_1},F_n)=(F_{r_1},F_n)$ (co tak偶e jest prost膮 w艂asno艣ci膮 NWD) Zastosowali艣my tu w zasadzie algorytm Euklidesa. Stosuj膮c go dalej otrzymujemy ci膮g reszt $r_k$, ostatnia reszta niezerowa jest oczywi艣cie r贸wna $(n,m)$. Dostajemy wi臋c $(F_m,F_n)=(F_{(n,m)},...)\le F_{(n,m)}$ ----- Dodam, 偶e jest to naprawd臋 ciekawe zadanie, bo trzeba kilku w艂asno艣ci u偶y膰 i troch臋 pomy艣le膰. Gdzie takie serwuj膮? By艂o obowi膮zkowe? |
| strony: 1 | |
Prawo do pisania przys艂uguje tylko zalogowanym u偶ytkownikom. Zaloguj si臋 lub zarejestruj