Bello, un altro problema sulle estensioni quadratiche!
Già che ci sono quindi provo a generalizzarlo a tutte le sequenze di Lucas...
Siano $S,P$ due interi coprimi e $D=S^2-4P$;
sia $a_0=0,a_1=1,a_{n+1}=Sa_n-Pa_{n-1}$ una successione (di interi ovviamente);
siano poi $\alpha,\beta$ le due radici di $x^2-Sx+P$, ovvero $\alpha=\dfrac{S+\sqrt D}2, \;\beta=\dfrac{S-\sqrt D}2$.
(Nota: i Fibonacci corrispondono a $S=1,P=-1,\alpha=\varphi,\beta=1-\varphi$)
Lemma noto $$a_n=\dfrac{\alpha^n-\beta^n}{\alpha-\beta}$$
Bene, questo fatto ci fa chiaramente vedere la correlazione della sequenza con degli esponenti; inoltre ciò che dobbiamo dimostrare è molto simile a LTE, quindi... ricicliamo la dimostrazione di LTE!
Ovvero:
- se $p\nmid k$ e $p\mid a_n$ allora $v_p(a_{nk})=v_p(a_n)$
- $v_p(a_{np})=v_p(a_n)+1$ nei due step (divide e divide esattamente)
- induzione banale per concludere
Per sicurezza escludiamo dalla dimostrazione il $2$ e i primi che dividono $S,D$ o $P$. (nel caso dei Fibonacci solo il $5$)
Step 1. $\displaystyle p\nmid k,\;p\mid a_n\implies v_p(a_{nk})=v_p(a_n)$
La nostra ipotesi è che $\dfrac{\alpha^n-\beta^n}{\alpha-\beta}\equiv0\pmod p$, da cui $\alpha^n\equiv\beta^n\pmod p$. Ora, per il lemma abbiamo $a_{nk}=\dfrac{\alpha^{nk}-\beta^{nk}}{\alpha-\beta}=\dfrac{\alpha^n-\beta^n}{\alpha-\beta}\left(\alpha^{n(k-1)}+\alpha^{n(k-2)}\beta^n+\dots+\beta^{n(k-1)}\right)$. Dobbiamo allora dimostrare che $p$ non divide il mostro nella parentesi, dato che abbiamo fattorizzato un $a_n$; sfruttando il fatto che $\alpha^n\equiv\beta^n\pmod p$ otteniamo che $\alpha^{n(k-1)}+\alpha^{n(k-2)}\beta^n+\dots+\beta^{n(k-1)}\equiv k\alpha^{n(k-1)}\pmod p$. Distinguiamo ora i casi se $D$ è residuo quadratico o no; se lo è, nessun problema, $\alpha$ esiste davvero modulo $p$, e dato che $p\nmid k$ e $p\nmid\alpha$ (per la supposizione $p\nmid P$) il mostro non è divisibile per $p$ e abbiamo fatto; se $D$ non è residuo quadratico, andiamo in $\mathbb Z[\sqrt D]$, ma allora $p$ è primo anche in quell'oggetto (lo lascio a chi vuole) e quindi concludiamo come prima (perché siamo infatti in un dominio d'integrità).
Dunque abbiamo dimostrato lo step 1.
Step 2. $\displaystyle p\mid a_n\implies v_p(a_{np})=v_p(a_n)+1$
Come sopra, dal lemma abbiamo che $a_{np}=a_n\left(\alpha^{n(p-1)}+\dots+\beta^{n(p-1)}\right)$. Dobbiamo quindi dimostrare che nella somma c'è esattamente un fattore $p$ e lo facciamo dicendo che ce n'è almeno uno (parte a) e ce n'è al più uno (parte b).
Inoltre abbiamo $\alpha^n\equiv\beta^n\pmod p\;\;(\ast)$ dal fatto che $p\mid a_n$.
Parte a. $\displaystyle p\mid \alpha^{n(p-1)}+\dots+\beta^{n(p-1)}$
Si ha grazie a $(\ast)$ che $\alpha^{n(p-1)}+\dots+\beta^{n(p-1)}\equiv p\alpha^{n(p-1)}\equiv0\pmod p$, che è quello che volevamo dimostrare.
Parte b. $\displaystyle p^2\nmid \alpha^{n(p-1)}+\dots+\beta^{n(p-1)}$
Da $(\ast)$ possiamo scrivere $\alpha^n=\beta^n+h\sqrt Dp$ con $h$ intero. Chiamiamo $k=h\sqrt D$, $x=\alpha^n$, $y=\beta^n$. Vediamo ora che $\displaystyle x^iy^{p-1-i}=(y+kp)^iy^{p-1-i}=(y^i+ikpy^{i-1}+\binom i 2 y^{i-2}(kp)^2+\dots)y^{p-1-i}$; ma se guardiamo modulo $p^2$ otteniamo $x^iy^{p-1-i}\equiv(y^i+ikpy^{i-1})y^{p-1-i}\equiv y^{p-1}+ikpy^{p-2}\pmod{p^2}$. Quindi finalmente abbiamo che $\alpha^{n(p-1)}+\dots+\beta^{n(p-1)}\equiv p\beta^{n(p-1)}+kp\beta^{n(p-2)}(1+2+\dots+(p-1))\equiv p\beta^{n(p-1)}+\dfrac{p(p-1)}2kp\beta^{n(p-2)}\equiv p\beta^{n(p-1)}\pmod{p^2}$; ma come nello step 1 abbiamo che $p\nmid\beta^{n(p-1)}$, quindi $p^2\nmid p\beta^{n(p-1)}$ e abbiamo finito lo step 2.
Step 3. $\displaystyle p\mid a_n\implies v_p(a_{nk})=v_p(a_n)+v_p(k)$
Per induzione, applichiamo ripetutamente lo step 2 finché esauriamo i fattori $p$ di $k$, e poi usiamo lo step 1 per dire che non ci sono altri fattori $p$.
Sono piuttosto sicuro che funzioni, ma non essendo ancora molto esperto potrebbe essermi sfuggita qualche sottigliezza che renderà tutti questi conti inutili (ma anche no xD)
