Dubbi sulle Pell

[Gerald Lambeau]

Ho provato di recente a guardare le equazioni di Pell e cercando le soluzioni intere positive $(x, y)$ dell'equazione di tipo Pell $x^2-3y^2=13$ trovo che deve essere $x+y\sqrt{3}=(4+\sqrt{3})(2+\sqrt{3})^n$, solo che così non trovo la soluzione $(x, y)=(16, 9)$. Dove sbaglio?

[AlexThirty]

Non sono sicuro di quello che ti sto per dire, dato che le Pell non le ho ancora guardate bene... ma le Pell non dicono solo che se esiste una soluzione non banale allora ne esistono infinite; ma non è detto che quelle che trovi in quella forma siano effettivamente tutte?

[<enigma>]

deve essere $x+y\sqrt{3}=(4+\sqrt{3})(2+\sqrt{3})^n$

No.
Che tutte le soluzioni si trovino con le potenze della soluzione fondamentale vale per l'equazione di Pell vera $x^2-dy^2=1$. Se invece di $1$ hai altri numeri nessuno ti dice che le trovi tutte (anche se chiaramente ne puoi trovare infinite... c'è un modo algoritmico per trovarle tutte ma nessun modo veramente pratico). Vai a riguardarti come si dimostra questo fatto, e vedi cosa non va se invece di $1$ hai $13$.

[Gerald Lambeau]

Grazie mille, era quasi palese che l'unico problema era che non le trovassi tutte, riguarderò la parte che mi manca.

[darkcrystal]

Sì, è una cosa che non si trova spessissimo spiegata in dettaglio... ho cercato di raccontare un po' come funzionassero le cose l'anno scorso al senior, http://olimpiadi.dm.unibo.it/videolezio ... rystal.pdf, ma se ben ricordo senza dimostrare tutto, e avevamo fatto qualcosa anche al Senior 2010 (alla fine del PDF). In due parole, quello che succede se guardi un'equazione del tipo $x^2-dy^2=m$ (dove $m$ non è necessariamente 1) è che ci possono essere più famiglie di soluzioni (il numero di famiglie* è al più $\varphi(|m|)$). Per esempio, per la tua equazione $x^2-3y^2=13$ abbiamo $\varphi(13)=12$, quindi ci possono essere un sacco di famiglie di soluzioni! Due soluzioni $(x,y)$ e $(z,w)$ appartenenti a "famiglie" diverse si distinguono calcolando $x \cdot y^{-1} \pmod {13}$ e $z \cdot w^{-1} \pmod {13}$: per meglio dire, due soluzioni appartengono a famiglie diverse se e solo se quel "rapporto" modulo 13 è diverso. Nel tuo caso, per la soluzione $(4,1)$ hai $4 \cdot 1^{-1} \equiv 4 \pmod {13}$, mentre per $(16,9)$ hai $16 \cdot 9^{-1} \equiv 3*3 \equiv 9 \pmod {13}$, e le due soluzioni in effetti appartengono a due famiglie diverse.

In ogni famiglia puoi identificare una soluzione "ridotta" che - in valore assoluto - sta nell'intervallo $\sqrt{m/f} , \sqrt{mf}$, dove $m$ per noi è 13 e $f$ è la soluzione fondamentale della Pell $x^2-dy^2$ (con $f>1$) - per noi, $f=2+\sqrt{3}$. Ad esempio, nel tuo caso la soluzione ridotta che porta a $16+9\sqrt{3}$ è $4-\sqrt{3}$, per la quale hai $16+9\sqrt{3} = (4-\sqrt{3})(2+\sqrt{3})^2$. Nota che se calcolo "x/y modulo 13" per identificare la famiglia trovo giustamente $4 \cdot (-1)^{-1} \equiv -4 \equiv 9 \pmod {13}$, quindi questa soluzione appartiene effettivamente alla stessa famiglia di $16+9\sqrt{3}$. Osserva anche che ho detto che ci sono al più $\varphi(13)=12$ famiglie per la tua equazione: in realtà ce ne sono solo 2, e con le cose dei PDF che ti ho linkato dovresti essere in grado di dimostrarlo (esercizio!): in altre parole, ogni soluzione della tua Pell si scrive
\[
x+\sqrt{3}y = \pm (4 \pm \sqrt{3}) \cdot (2+\sqrt{3})^n
\]
dove possiamo scegliere i due segni e l'intero $n$ (positivo, negativo o zero) come vogliamo. E' un po' più chiaro?



* per meglio dire, di famiglie "primitive", dove "primitivo" vuol dire che $x,y$ sono primi tra loro. Ma qui è automatico: se $x,y$ hanno un fattore primo in comune, allora questo fattore primo divide anche 13, quindi è proprio 13. Ma allora $13^2$ divide $x^2-3y^2=13$, assurdo!

[Gerald Lambeau]

Innanzitutto grazie mille per l'aiuto e per l'utilissima spiegazione!
Vediamo un po' se la mia soluzione all'esercizio che mi hai proposto è giusta: con le stesse considerazione che hai fatto tu trovo che nessuno dei due è multiplo di $13$ e questo giustifica tutti i passaggi che sto per andare a fare. Dalla mia equazione mi ricavo $x^2 \equiv 3y^2 \pmod{13} \Rightarrow (x \cdot y^{-1})^2 \equiv 3 \pmod{13}$ che ha come uniche due soluzioni $x \cdot y^{-1} \equiv 4 \pmod{13} \lor x \cdot y^{-1} \equiv 9 \pmod{13}$, quindi ci sono solo due famiglie di soluzioni.

[darkcrystal]

Yep, perfetto! E chiaramente questo si generalizza: se guardo una Pell $x^2-dy^2=p$, dove $p$ è primo e non divide $d$, allora ci sono al massimo due famiglie di soluzioni (il che è una stima molto migliore di $\varphi(p)=p-1$, di solito ), perché $x \cdot y^{-1} \pmod p$ deve essere una radice quadrata di $d$ modulo $p$, e modulo $p$ ci sono - al massimo - due radici quadrate di ogni numero.