Feladat:	N.67	Korcsoport: 18-	Nehézségi fok: nehéz
Megoldó(k):	Braun Gábor ,  Burcsi Péter ,  Farkas Péter ,  Gyarmati Katalin ,  Izsák Ferenc ,  Makai Márton ,  Pap Gyula ,  Póczos Barnabás ,  Szádeczky-Kardoss Szabolcs ,  Tóth Gábor Zsolt ,  Valkó Benedek
Füzet:	1996/április, 224 - 226. oldal		PDF  |  MathML
Témakör(ök):	Oszthatóság, Konstruktív megoldási módszer, Nehéz feladat
Hivatkozás(ok):	Feladatok: 1995/április: N.67

A szöveg csak Firefox böngészőben jelenik meg helyesen. Használja a fenti PDF file-ra mutató link-et a letöltésre.   I. megoldás. Legyen $f_1=1$, $f_2=1$, $f_3=2$, $f_4=3$, $f_5=5$, $f_6=8$, $\text{...}$ a Fibonacci-sorozat. Azt állítjuk, hogy az $\left(f_{2k+1}\mathrm{,}{f}_{2k+3}\right)$ alakú számpárok megfelelők lesznek. Mivel ezek a számpárok páronként különbözőek, a konstrukció végtelen sok megoldást állít elő. Bebizonyítjuk, hogy minden $k$ pozitív egészre $\begin{array}{c}{\displaystyle f_{2k+1}^2+1=f_{2k-1}{f}_{2k+3}\mathrm{.}}\end{array}$ (1) Ebből állításunk következik, mert $\begin{array}{c}{\displaystyle \frac{f_{2k+1}^2+1}{f_{2k+3}}=f_{2k-1}\text{és}\frac{f_{2k+3}^2+1}{f_{2k+1}}=f_{2k+5}}\end{array}$ is egész szám lesz. Az (1) azonosságot teljes indukcióval igazoljuk. Az állítás igaz $k=1$-re, mert $f_3^2+1=2^2+1=1\cdot 5=f_1{f}_5$. Tegyük fel, hogy (1) valamilyen $k$-ra teljesül, és hogy $m\ge 3$ esetén $\begin{array}{c}{\displaystyle {\displaystyle \begin{array}{c}\hfill {\displaystyle f_{m+2}+f_{m-2}=f_{m+1}+f_m+f_{m-2}=\left(f_m+f_{m-1}\right)+f_m+f_{m-2}=}\\ \hfill {\displaystyle =2f_m+\left(f_{m-1}+f_{m-2}\right)=3f_m\mathrm{,}}\end{array}}}\end{array}$ ebből következik az állítás $\left(k+1\right)$-re: $\begin{array}{c}{\displaystyle {\displaystyle \begin{array}{c}\hfill {\displaystyle f_{2k+3}^2+1=\left(f_{2k+3}^2-f_{2k+1}^2\right)+\left(f_{2k+1}^2+1\right)=f_{2k+3}^2-f_{2k+1}^2+f_{2k-1}{f}_{2k+3}=}\\ \hfill {\displaystyle =f_{2k+3}^2-f_{2k+1}^2+\left(3f_{2k+1}-f_{2k+3}\right)f_{2k+3}=f_{2k+1}\left(3f_{2k+3}-f_{2k+1}\right)=f_{2k+1}{f}_{2k+5}\mathrm{.}}\end{array}}}\end{array}$ Az (1) azonosság tehát minden $k$-ra teljesül.  Valkó Benedek (Fazekas M. Főv. Gyak. Gimn., IV. o. t.)   Megjegyzés. Az (1) azonosság a Fibonacci-sorozat alábbi ismert explicit alakjából is bebizonyítható: $\begin{array}{c}{\displaystyle f_k=\frac{{\left(\frac{1+\sqrt[]{5}}{2}\right)}^{k+1}-{\left(\frac{1-\sqrt[]{5}}{2}\right)}^{k+1}}{\sqrt[]{5}}\mathrm{.}}\end{array}$   II. megoldás. Ha $m\mid n^2+1$ és $n\mid m^2+1$, akkor $m$ és $n$ relatív prímek. Ha ugyanis $m$ és $n$ legnagyobb közös osztója $d$, akkor $d\mid m\mid n^2+1$ miatt $d\mid 1$. Mivel $m^2+n^2+1$ osztható $m$-mel és $n$-nel is, a relatív prímség miatt osztható $mn$-nel is. Megfordítva, ha $m^2+n^2+1$ osztható $mn$-nel, akkor osztható $m$-mel és $n$-nel is, amiből következik, hogy $m\mid n^2+1$ és $n\mid m^2+1$. A feltétel tehát azzal ekvivalens, hogy $m^2+n^2+1$ osztható $mn$-nel. Legyen $a$ pozitív egész, és tekintsük az $\begin{array}{c}{\displaystyle x^2+y^2+1=axy}\end{array}$ (2) egyenletet. Azt állítjuk, hogy ha ennek van pozitív egészekből álló megoldása, akkor végtelen sok is van. Ebből az állítás azonnal következik. Tegyük fel, hogy $\left(x_0\mathrm{,}{y}_0\right)$ egy megoldása (2)-nek, és $x_0\le y_0$. Ha (2)-t egy paraméteres másodfokú egyenletnek tekintjük, amelyben $x$ az ismeretlen, akkor az egyenlet egyik gyöke $x_0$, a másik pedig a gyökök és együtthatók közötti összefüggések (ViŠta formulák) alapján $\begin{array}{c}{\displaystyle x_1=a{y}_0-x_0=\frac{y_0^2+1}{x_0}\mathrm{.}}\end{array}$ Az első formula alapján ez a gyök is egész, a második szerint pedig pozitív, sőt $\begin{array}{c}{\displaystyle x_1=\frac{y_0^2+1}{x_0}>\frac{y_0^2}{y_0}=y_0\mathrm{.}}\end{array}$ A (2) egyenletnek ezért az $\left(x_1\mathrm{,}{y}_0\right)$ számpár egy újabb, pozitív egészekből álló megoldása, amelyben a két szám összege nagyobb, mint az előzőben: $x_1+y_0>x_0+y_0$. A megoldások között tehát nincs olyan, amelyben a két ismeretlen összege maximális. Ha $a=3$, akkor (2)-nek van megoldása, például $x=y=1$. Az előbbiek szerint ebből következik, hogy végtelen sok olyan $\left(m\mathrm{,}n\right)$ számpár van, amelyre teljesül, hogy $m^2+n^2+1=3mn$.  Tóth Gábor Zsolt (Budapest, Árpád Gimn., III. o.t.) és    Braun Gábor (Budapest, Szent István Gimn., II. o.t) dolgozata nyomán   Megjegyzések. 1. A két megoldás lényegében ugyanazokat a számpárokat adja. A II. megoldásban adott konstrukció ugyanis az $\left(m\mathrm{,}n\right)$ számpárból az $\left(n\mathrm{,3}m-n\right)$ számpárt állítja elő, ami megfelel az $f_{m+2}=3f_m-f_{m-2}\mathrm{,}$ rekurziónak. Az $\left(\mathrm{1,1}\right)$ számpárt az I. megoldás is előállítja, ha bevezetjük az $f_0=0$, $f_{-1}=1$ elemeket. 2. A második megoldás módszerével nem nehéz bebizonyítani, hogy más megoldás nincs. Ehhez először azt mutatjuk meg, hogy (2)-nek csak $a=3$ esetén van pozitív egészekből álló megoldása. Tekintsünk egy olyan $\left(x_0\mathrm{,}{y}_0\right)$ megoldást, amelyben $x_0+y_0$ minimális. Ha $x_0=y_0=1$, akkor $a=3$ és kész vagyunk. Ellenkező esetben feltehetjük, hogy $x_0>y_0$ (egyenlők nem lehetnek, mert relatív prímek). Definiáljuk most ismét az $\begin{array}{c}{\displaystyle x_1=a{y}_0-x_0=\frac{y_0^2+1}{x_0}}\end{array}$ számot. Ez ismét pozitív egész lesz, de ezúttal $\begin{array}{c}{\displaystyle x_1=\frac{y_0^2+1}{x_0}\le \frac{y_0^2+y_0}{y_0+1}=y_0<x_0\mathrm{.}}\end{array}$ Az $\left(x_1\mathrm{,}{y}_0\right)$ számpár tehát olyan pozitív egészekből álló megoldás, amelyben $x_1+y_0<x_0+y_0$. Ez viszont ellentmondás, mert feltettük, hogy $x_0+y_0$ minimális. Ezután már nem nehéz bebizonyítani, hogy ha $x\le y$ egy megoldása (2)-nek, akkor $x=f_{2k-1}$ és $y=f_{2k+1}$ valamilyen $k$ nemnegatív egésszel. Ez ismét teljes indukcióval történhet. Ha $x+y\le 2$, akkor az állítás triviális. Tegyük fel, hogy igaz $x+y<M$ esetén. Ebből bebizonyítjuk $x+y=M$-re is. Legyen $x<y$ egy olyan megoldása (2)-nek, amelyben $x+y=M$ és $M\ge 4$. Mivel az $\left(x\mathrm{,3}x-y\right)=\left(x\mathrm{,}\frac{x^2+1}{y}\right)$ is pozitív egészekből álló megoldás, de ebben $\frac{x^2+1}{y}<x$ és $x+\frac{x^2+1}{y}<x+y=M$, az indukciós feltevés szerint létezik olyan $k$ nemnegatív egész szám, amelyre $3x-y=f_{2k+1}$ és $x=f_{2k+3}$. Ebből viszont következik, hogy $y=3f_{2k+3}-f_{2k+1}=f_{2k+5}$.