177. Brutta sequenza modulo p

[Troleito br00tal]

Own, purtroppo. Sia $p \equiv 1 \pmod{3}; p \not \equiv 7 \pmod{8}$ primo. Sia $1 \le n \le p$ un intero positivo e sia $a_0=n;a_{i+1}=a_i^2-2$. Determinare in funzione di $p$ per quanti valori di $n$ esiste un $k$ tale che $a_{k+1} \equiv a_k \pmod{p}$.

[Gottinger95]

Ma davvero sei così crudele che \(p \equiv 1 \pmod{3}\),oppure è un typo e volevi scrivere \(p \equiv 2 \pmod{3}\)?

[Troleito br00tal]

È più facile? Wow figo, io ho risolto con $1$ e non con $2$

[darkcrystal]

Disclaimer: il conto l'ho fatto un po' di fretta, quindi potrei essermi sbagliato. Comunque, rilancio: mostrare o che mi sono sbagliato, o che per ogni primo vale
\[
\left|\left\{\mbox{cose che vuol contare Troleito} \right\}\right|= \frac{\left(p+1,3\cdot 2^{\infty}\right) + \left(p-1,3\cdot 2^{\infty}\right)}{2},
\]
dove $\left(n,3\cdot 2^{\infty}\right)$ vuol dire il più grande intero positivo che divide sia $n$ che almeno un intero della forma $3 \cdot 2^k, k \in \mathbb{N}$ (equivalentemente, la più grande potenza di 2 che divide $n$ moltiplicata per $(n,3)$)

Have fun !

[Troleito br00tal]

Disclaimer: il conto l'ho fatto un po' di fretta, quindi potrei essermi sbagliato. Comunque, rilancio: mostrare o che mi sono sbagliato, o che per ogni primo vale
\[
\left|\left\{\mbox{cose che vuol contare Troleito} \right\}\right|= \frac{\left(p+1,3\cdot 2^{\infty}\right) + \left(p-1,3\cdot 2^{\infty}\right)}{2},
\]
dove $\left(n,3\cdot 2^{\infty}\right)$ vuol dire il più grande intero positivo che divide sia $n$ che almeno un intero della forma $3 \cdot 2^k, k \in \mathbb{N}$ (equivalentemente, la più grande potenza di 2 che divide $n$ moltiplicata per $(n,3)$)

Have fun !

Dovrebbe essere vero (o almeno, anche a me veniva una cosa molto simile)! Ho messo le condizioni su $p$ perché ho trovato un modo totalmente elementare per farlo solo con quelle condizioni:)

Oppure hai un modo elementare per farlo?

[Triarii]

Qualche hint? Ho risolto l'equazione iniziale mod p, però poi se continuo mi viene fuori una specie di catena infinita di possibilità che non si ferma più...

[Troleito br00tal]

È vero che esiste ancora questo problema!

Hint

Testo nascosto:

Consideriamo la sostituzione $a=x+\frac{1}{x}$. Quando si può fare? Quando non si può fare? Perché è molto pregia?

[Drago96]

Oh wow è quella che avevo pensato, ed ero arrivato molto vicino al bonus di darkcrystal... la riguardo un po', poi posto qualcosa

[Troleito br00tal]

Up? Diamo un hint peso:

Diciamo che $x$ è bello se esiste $\lambda$ tale che $x=\lambda+\frac{1}{\lambda}$. Ora, questa cosa si può fare se solo se $x$ è radice di una certa equazione di secondo grado. Dimostriamo ora che, a parte casi particolari, $x$ è bello se e solo se $x^2-2$ è bello. E da qui si dovrebbe concludere (generatori).

[jordan]

Ci fermiamo qui?

[Troleito br00tal]

Ho postato un altro problema per la staffetta. Fra qualche giorno scrivo la soluzione di questo.