Zadania z kółek matematycznych lub obozów przygotowujących do OM. Problemy z minionych olimpiad i konkursów matematycznych.
Regulamin forum
Wszystkie tematy znajdujące się w tym dziale powinny być tagowane tj. posiadać przedrostek postaci [Nierówności], [Planimetria], itp.. Temat może posiadać wiele różnych tagów. Nazwa tematu nie może składać się z samych tagów.
Udowodnić, że jeśli dodatnie całkowite \(\displaystyle{ n}\) NIE jest postaci \(\displaystyle{ 2 ^{y} 3 ^{x}}\) (gdzie \(\displaystyle{ x}\) i \(\displaystyle{ y}\) są całkowite nieujemne), to \(\displaystyle{ F _{n}}\) ma co najmniej jeden dzielnik pierwszy postaci \(\displaystyle{ 4k + 1}\) (gdzie \(\displaystyle{ k}\) jest całkowite dodatnie).-- 4 cze 2013, o 08:49 --no i \(\displaystyle{ F _{n}}\) to n-ty wyraz ciągu Fibonacciego.
Zacznijmy od kilku własności ciągu Fibonacciego. \(\displaystyle{ F_{2n-1}=F_{n}^{2}+F_{n-1}^{2} \\
F_{2n}=F_{n+1}^{2}-F_{n-1}^{2}}\)
Udowodnię je indukcyjnie dla \(\displaystyle{ n=1}\) zgadza się. Przejdźmy do kroku indukcyjnego \(\displaystyle{ F_{2n+1}=F_{2n}+F_{2n-1}=F_{n+1}^{2}-F_{n-1}^{2}+F_{n}^{2}+F_{n-1}^{2}=F_{n+1}^{2}+F_{n}^{2} \\
F_{2n+2}=F_{2n+1}+F_{2n}=F_{n+1}^{2}+F_{n}^{2}+F_{n+1}^{2}-F_{n-1}^{2}= \\F_{n+1}^{2}+F_{n}^{2}+F_{n}^{2}+2F_{n}F_{n-1}+F_{n-1}^{2}-F_{n-1}^{2}= F_{n+1}^{2}+2F_{n}(F_{n-1}+F_{n})= \\ F_{n+1}^{2}+2F_{n}F_{n+1} = (F_{n+1}+F_{n})^{2}-F_{n}^{2}=F_{n+2}^{2}-F_{n}^{2}}\)
Potrzebny nam będzie jeszcze fakt, że jeśli \(\displaystyle{ k|n}\) to \(\displaystyle{ F_{k}|F_{n}}\) Udowadnia się go korzystając z własności \(\displaystyle{ F_{n+1}F_{m}+F_{n}F_{m-1}=F_{m+n}}\), którą udowadnia ją się indukcyjnie. Potrzeby nam będzie jeszcze wniosek, że \(\displaystyle{ 3|n \Leftrightarrow 2|F_{n}}\) Co łatwo widać analizując \(\displaystyle{ \pmod{2}}\) ciągu.
Teraz przejdźmy do dowodu. Z tezy mamy, że istnieje takie \(\displaystyle{ l>1}\) , że \(\displaystyle{ 2\nmid l \ \ 3\nmid l \ \ l|n}\). Korzystając z trzeciego faktu mamy \(\displaystyle{ F_{l}|F_{n}}\). Z uwagi na pierwszą zależność mamy \(\displaystyle{ F_{l}=F_{\frac{l+1}{2}}^{2}+F_{\frac{l-1}{2}}^{2}}\). Korzystając ostatniego faktu widać, że \(\displaystyle{ 2 \nmid F_{l}}\). Z uwagi na to, że \(\displaystyle{ NWD(F_{\frac{l+1}{2}},F_{\frac{l-1}{2}})=1}\) mamy, że jeśli liczba pierwsza \(\displaystyle{ p|F_{\frac{l+1}{2}}^{2}+F_{\frac{l-1}{2}}^{2}}\), to \(\displaystyle{ p}\) nie dzieli się przez żadny z czynników. Teraz jeśli \(\displaystyle{ p\equiv 3 \pmod{4}}\) To otrzymujemy sprzeczność, bo korzystając z reszt kwadrtowych mamy \(\displaystyle{ F_{\frac{l+1}{2}}^{2}\equiv - F_{\frac{l-1}{2}}^{2} \pmod{p} \Rightarrow 1=\left( \frac{F_{\frac{l+1}{2}}^{2}}{p} \right)=\left( \frac{-1}{p}\right) \cdot \left( \frac{F_{\frac{l-1}{2}}^{2}}{p} \right)= \left( \frac{-1}{p}\right)=(-1)^{\frac{p-1}{2}}=-1}\).
Z tego wynika \(\displaystyle{ p\equiv 1\pmod{4}}\), co z tym, że \(\displaystyle{ p|F_{l} \ \hbox{i} \ F_{l}|F_{n}}\) Udowadnia tezę zadania
