 |
Az A. 730. feladat (2018. szeptember) |
A. 730. Legyen \(\displaystyle F_n\) az \(\displaystyle n\)-edik Fibonacci-szám (\(\displaystyle {F_1=F_2=1}\), \(\displaystyle {F_{n+1}=F_n+F_{n-1}}\)). Konstruáljunk végtelen sok olyan \(\displaystyle n\) pozitív egész számot, amelyre \(\displaystyle F_{F_n}\) osztható \(\displaystyle n\)-nel, de \(\displaystyle F_n\) nem osztható \(\displaystyle n\)-nel.
(7 pont)
A beküldési határidő 2018. október 10-én LEJÁRT.
Megoldás (vázlat). Megmutatjuk, hogy \(\displaystyle n=4\cdot3^k\cdot23\) tetszőleges \(\displaystyle k\) pozitív egésszel teljesíti a feltételeket.
Fel fogjuk használni a Fibonacci-számok néhány jól ismert tulajdonságát.
1. lemma. \(\displaystyle 3\big|F_n\) esetén \(\displaystyle v_3(F_{3n})=v_3(F_n)+1\). (\(\displaystyle v_p(k)\) jelöli a \(\displaystyle p\) prímszám kitevőjét a \(\displaystyle k\) prímtényezős felbontásában.)
Bizonyítás. Legyen \(\displaystyle \varphi=\frac{1+\sqrt5}2\) és \(\displaystyle \psi=\frac{1-\sqrt5}2\). A Fibonacci számok zárt alakját felhasználva,
\(\displaystyle F_{3n} = \frac{\varphi^{3n}-\psi^{3n}}{\sqrt5} = \frac{(\varphi^n-\psi^n)^3+3\varphi^n\psi^n(\varphi^n-\psi^n)}{\sqrt5} = 5\bigg(\frac{\varphi^n-\psi^n}{\sqrt5}\bigg)^3+3(\varphi\psi)^n\frac{\varphi^n-\psi^n}{\sqrt5} = 5F_n^3+3(-1)^nF_n. \)
A \(\displaystyle 3\) kitevője az \(\displaystyle 5F_n^3\) tagban \(\displaystyle 3v_3(F_n)\), a \(\displaystyle 3(-1)^nF_n\)-ban \(\displaystyle v_3(F_n)+1\); a második kitevő kisebb, mint az első.
2. lemma. \(\displaystyle 23\big|F_n \,\Longleftrightarrow 24\big|n\).
Bizonyítás. Könnyű ellenőrizni, hogy az első Fibonacci-szám, amely osztható \(\displaystyle 23\)-mal, az \(\displaystyle F_{24}=46368=2016\cdot 23\).
Ha \(\displaystyle 24\big|n\), akkor \(\displaystyle 23\big|F_{24}\big|F_n\).
Ha \(\displaystyle 24\not{\big|}n\), akkor legyen \(\displaystyle d=(n,24)<24\). Ekkor \(\displaystyle (F_n,23)\big|(F_n,F_{24})=F_d\), de \(\displaystyle F_d\), lévén \(\displaystyle F_{24}\)-nél korábbi Fibonacci-szám, nem osztható \(\displaystyle 23\)-mal.
Ezek után, ha \(\displaystyle k\ge1\) és \(\displaystyle n=4\cdot3^k\cdot23\), akkor a 2. lemma miatt \(\displaystyle n\not{\big|}F_n\), mert \(\displaystyle 23\not{\big|}F_n\), mert \(\displaystyle 24\not{\big|}n\).
Másrészt,
- \(\displaystyle 12\big|n\) miatt \(\displaystyle 24\big|144=F_{12}\big|F_n\);
- \(\displaystyle 12\big|F_n\) miatt \(\displaystyle 144=F_{12}\big|F_{F_n}\);
- \(\displaystyle 3\big|F_4\big|F_{4\cdot23}\), és az 1. lemma miatt \(\displaystyle 3^k\big|F_n\), majd \(\displaystyle 3^k\big|F_{F_n}\);
- \(\displaystyle 24\big|F_n\) miatt \(\displaystyle 23\big|F_{F_n}\).
... tehát \(\displaystyle F_{F_n}\) osztható \(\displaystyle n=4\cdot3^k\cdot23\)-mal.
Megjegyzés. Kicsit általánosabban: a Fibonacci számokat iterálva legyen \(\displaystyle F^k(n)=\underbrace{F(\ldots F}_k(n)\dots)\); ekkor minden \(\displaystyle k\ge2\)-höz létezik végtelen sok \(\displaystyle n\) úgy, hogy \(\displaystyle n\big|F^k(n)\), de \(\displaystyle n\) nem osztja \(\displaystyle F(n),\ldots,F^{k-1}(n)\) egyikét sem.
Bizonyítás: Legyen \(\displaystyle m\) olyan, amelyre \(\displaystyle m\big|F_m\) (pl. lehet \(\displaystyle m=5^t\) vagy \(\displaystyle m=12\cdot 3^t\) vagy \(\displaystyle m=F^t(12)\) stb.). Legyen \(\displaystyle p\) az \(\displaystyle F^k(m)\) egy primitív prímosztója (ha \(\displaystyle m\) elég nagy, akkor a Carmichael-tétel miatt van neki), és legyen \(\displaystyle n=mp\). Ekkor \(\displaystyle m\big|F(m)\big|F^2(m)\big|\ldots\big|F^k(m)\) és \(\displaystyle p\big|F^k(m)\), ezért \(\displaystyle n\big|F^k(m)\big|F^k(n)\).
Másrészt \(\displaystyle 1\le\ell<k\) esetén
\(\displaystyle \gcd\big(F^\ell(n),n\big) \big| \gcd\big(F^\ell(n),F^k(n)\big) = F^\ell\big(\gcd(F^{k-\ell}(n),n)\big), \)
itt \(\displaystyle F^{k-\ell}(n)\) nem osztható \(\displaystyle p\)-vel, ezért
\(\displaystyle \gcd\big(F^\ell(n),n\big) \Big| m, \)
emiatt
\(\displaystyle \gcd\big(F^\ell(n),n\big) \big| F^\ell\big(m)\big), \)
amit megint csak nem osztható \(\displaystyle p\)-vel.
Statisztika:
10 dolgozat érkezett. 7 pontot kapott: Jedlovszky Pál, Kerekes Anna, Matolcsi Dávid, Schrettner Jakab, Szabó 991 Kornél, Szabó Kristóf. 6 pontot kapott: Beke Csongor. 0 pontot kapott: 2 versenyző. Nem számítjuk a versenybe a születési dátum vagy a szülői nyilatkozat hiánya miatt: 1 dolgozat.
A KöMaL 2018. szeptemberi matematika feladatai