QuasiFibonacci Coprimi

[EvaristeG]

Sia $k>1$ un intero e sia $m=4k^2-5$. Dimostrare che scegliendo opportunamente gli interi $a$, $b$, tutti i termini della successione definita da
$$x_{n+1}=x_n+x_{n-1}\qquad x_1=b\qquad x_0=a$$
sono coprimi con $m$.

(PreIMO2005 - TDN - pomeriggio)

[Visto che qualcuno ha chiesto di radici...]

[Ido Bovski]

Chiamiamo per comodità $\displaystyle \varphi =\frac{1+\sqrt{5}}{2}$ e $\displaystyle \psi =\frac{1-\sqrt{5}}{2}$. Le radici del polinomio caratteristico $x^2-x-1$ sono $\varphi$ e $\psi$, allora $x_n=\alpha\varphi^n+\beta\psi^n$. Imponendo alla formula così trovata di essere valida per $n=0$ e $n=1$, si ha che $\displaystyle x_n=\frac{1}{\sqrt{5}}[(b-a\psi)\varphi^n+(a\varphi-b)\psi^n]$. Notiamo ora che $\sqrt{5}\equiv 2k$ e che $\displaystyle \frac{1}{2}\equiv \frac{4k^2-4}{2}\equiv 2k^2-2 \pmod m$. Allora scegliendo $a=1$ e $b\equiv 2k^2+k-2 \pmod m$, abbiamo che $x_n\equiv b^n \pmod m$. La scelta così fatta funziona poiché, per l'algoritmo di Euclide, $\gcd(m, b)=1$.

Col senno di poi si possono trovare soluzioni più concise, ma questa dovrebbe essere l'idea.

[EvaristeG]

Deprecabilmente scevro di dettagli, ma essenzialmente corretto.

[Ido Bovski]

Deprecabilmente scevro di dettagli

Vero