Teoria liczb, zadanie nr 1404

Autor	Zadanie / Rozwiązanie
polkiuyt postów: 34	2013-06-06 22:44:52 Pokaż, ż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