kaede wrote: $ \#\{a_{k}\bmod p;\ k\in \mathbb{N}\}$ What does this mean? I have never seen that before @below I mean what is the purpose of #{...} got it, thank you

@above $a_{n}\bmod p$ means the remainder when $a_{n}$ is divided by $p$ $\{a_{k}\bmod p;\ k\in \mathbb{N}\}$ means the set $\{a_{1}\bmod p,\ a_{2}\bmod p,\ ....\}$ If $A$ is a set, then $\#A$ means the number of elements of $A$.

Suppose on the contrary that $a_{n+1}$ and $2n+1$ has a common prime factor $p$. Let $f(x)=x^2-x-1$, then $$4f(x)\equiv (2x-1)^2-5 \pmod p \qquad(1)$$Now we easily have $(a_1,3)=(a_2,5)=1$. Consider $n\geq 2$. Consider the set $$S=\{a_2,...,a_n\}$$CLAIM. For all $a_i,a_j\in S$$(i\neq j)$, we have (i) $a_i\neq \pm 1\pmod p$ (ii) $a_i\neq 0\pmod p$ (iii) $a_i\neq a_j\pmod p$ Proof. (i) If $a_i\equiv 1\pmod p$ then $a_{i+2k+1}\equiv-1$ and $a_{i+2k}\equiv 1$ modulo $p$ for every natural number $k$, this contradicts the fact $a_{n+1}=0\pmod p$, similarly $a_i\equiv -1\pmod p$ is impossible. (ii) If $a_i\equiv 0\pmod p$, then $a_{i+1}\equiv -1\pmod p$, hence $i\neq n$, so $2\leq i\leq n-1$, but this implies $a_{i+1}\equiv -1\pmod p$, which contradicts (i) (iii) If $a_i\equiv a_j\pmod p$, then the sequence will be periodic modulo $p$. In particular, from (ii) the sequence will contain no terms with $a_i\equiv 0\pmod p$, contradicting $a_{n+1}\equiv 0\pmod p$. $\blacksquare$ Now, if $p\leq \frac{2n+1}{3}$, then there must exists $a_i=a_j$ by pigeonhole principle, contradicting (iii). Hence $p=2n+1$ Now consider the set $T=4S+5=\{4s+5|s\in S\}$. Then from $(1)$, the elements of $T$ are all quadratic residues modulo $p$, meanwhile from $(ii)$ it can't be equal to $1,9$ modulo $p$. Meanwhile, since $5$ is a quadratic residue mod $p$ from $(1)$, and $0\notin S$, $5\notin T$. There are only $p+1$ quadratic residues modulo $p$, and three of them can't be elements of $T$. From this, we conclude that there are at most $p-2$ choices for the elements in $T$, so by pigeonhole principle there exists two of them which are congruent modulo $p$, contradicting (iii) of the claim.

Huh? It suffices to show the result for primes $2n+1$, because if there is a sequence of length $n+1$ such that $a_{n+1}$ is divisible by $p\mid 2n+1$, then there is a sequence of length $\frac{p-1}2$ (as $a_1$ is arbitrary). Let $f(n)=n^2-n-1$ and consider a digraph on $0,\ldots,p-1$ and connect $a$ to $b$ if $f(a)\equiv b\pmod p$ ($p=2n+1$ for some $n$). Note $0$ goes to $-1$, which forms a 2-cycle with $1$. Now note as quadratics have either 0 or two roots (except in the lone case where the quadratic has a double root), and we have at most $2n-2=p-3$ possible numbers to continue to rearrange, we get that the maximum length of the sequence is \[\left\lfloor\frac{2n-1}2\right\rfloor+2\leq p+1\]as desired.

can't we take a_1 = 5 then gcd(a_2,2(1)+1)=gcd(21,3) = 3 then they are not co prime in fact any a_1 = 3k+2 works

kotmhn wrote: can't we take a_1 = 5 then gcd(a_2,2(1)+1)=gcd(21,3) = 3 then they are not co prime in fact any a_1 = 3k+2 works No. If $a_1=5$ then $a_2=5^2-5-1=19$ and $gcd(19,3)=1$.