logowanie

matematyka » forum » forum zadaniowe - uczelnie wyższe » zadanie

Teoria liczb, zadanie nr 1404

ostatnie wiadomości  |  regulamin  |  latex

AutorZadanie / 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





© 2019 Mariusz Śliwiński      o serwisie | kontakt   drukuj