Let $n=4\cdot p^t+1.$ Is $r_k=4$ for some $1\le kLet $n=4\cdot p^t+1$, $t\ge1$ and $p\ge5$ prime. 
Define sequence $R$ as follows; 
$r_0=4,$ $r_{k+1}\equiv r_k^2-2\pmod n$, $0\le r_k<n$ for $k\ge1$. 
It appears that whenever $n$ is prime,  $r_k=4$ for some  positive integer $k<n$. How does one go about proving this result for all primes $p\ge5$ and positive integers $t$? Are there any counter examples? (I have done a search for all $p<10^6$ with $t=1,2$. No counter examples.)
 A: Your conjecture is true
Any time one sees recurrence sequences like $r_0=4,r_{k+1}=r_{k}^2-2$, along with something to do with primality, the first thing one should do is think that the recurrence sequence is representing some multiplication in some group mod the prime. In this case this is true:
Let $w=2+\sqrt{3}$ and $\overline{w}=2-\sqrt{3}$. Then using the fact that
$w^{2^0}+\overline{w}^{2^0}=2+\sqrt{3}+2-\sqrt{3}=4$
and
$w\overline{w}=1$
we can easily deduce that $r_n=w^{2^n}+\overline{w}^{2^n}$. This recurrence $r_n$ is actually the same one used in the Lucas Lehmer test.
Now for some group theory. If $n>3$ is prime (for any $n$), then $(\mathbb{Z}/n\mathbb{Z})[x]/(x^2-3)$ is a group (this is simply notation for the set of algebraic integers $a+b\sqrt{3},a,b\in\mathbb{Z}/N\mathbb{Z}$, with normal complex multiplication, all modulo $N$). In this case, $(n/3)=-1$, so we can note that
$(2+\sqrt{3})^n\equiv 2^n+\sqrt{3}^n\equiv 2-\sqrt{3}\mod n$ by the Binomial Theorem in finite fields.
Thus $(2+\sqrt{3})^{n+1}\equiv (2+\sqrt{3})(2-\sqrt{3})\equiv 1\mod n$. And we can similarly see that $\overline{w}^{n+1}\equiv 1\mod n$. This means that $w^{{n+2}}+\overline{w}^{n+2}\equiv w+\overline{w}\equiv 4\mod n$. For certain reasons that will soon become clear (even vs odd), we have to take this a step further.
Similar to the proof of LL in the link above, define $\sigma=(6+2\sqrt{3})$ and $\overline{\sigma}=(6-2\sqrt{3})$. Notice that $\sigma^2/24=w$. But then by the binomial theorem in finite fields,
$w^{\frac{n+1}{2}}=\sigma^{n+1}/24^{\frac{n+1}{2}}=\sigma\sigma^{n}/24^{\frac{n+1}{2}}=\sigma\overline{\sigma}/(24\cdot 24^{\frac{n-1}{2}})\mod n$
From @mode_er's answer, we see that $(24/n)=1$, and we can directly compute that $\sigma\overline{\sigma}=24$, and thus
$w^{\frac{n+1}{2}}\equiv 1\mod n$, and symmetrically $\overline{w}^{\frac{n+1}{2}}\equiv 1\mod n$.
But $n=4p^t+1$, $n+1=4p^t+2=2(2p^t+1)$ only has one factor of $2$. Thus $\frac{n+1}{2}$ is odd. This is important because since $(n+1)/2$ is odd, $(n+1)/2|2^{\phi((n+1)/2)}-1$ (with $\phi(\bullet)$ Euler's totient function), and noting that $0<\phi((n+1)/2)<n$, we have that $m(n+1)/2=2^{j}-1$ for some $0<j<n$.
Thus $w^{2^j-1}=\overline{w}^{2^j-1}\equiv w^{m(n+1)/2}\equiv \overline{w}^{m(n+1)/2}\equiv 1^m=1\mod n$ and arguing similarly to above,
$r_j=w^{2^j}+\overline{w}^{{2^j}}=w^{2^j-1}w+\overline{w}^{2^j-1}\overline{w}\equiv w+\overline{w}\equiv 4\mod n$, with $0<j<n$, as desired. In fact due to construction with $\phi(\bullet)$ we can say $0<j<(n+1)/2$, a tighter bound.

Note that we only used part of the fact that $n=4p^t+1$ (although this form was slightly more important than I expected), and in fact this holds for any prime $n$, $n>3$ such that $n+1\equiv 2\mod 4$ (only one factor of $2$) such that $(2/n)=(3/n)=-1$.
A: I can't seem to find a solution using only elementary number theory. From what I did find, it's obvious that we need
$$r_{k-1}^2-2\equiv 4 \text{ mod } n$$
$$r_{k-1}^2\equiv 6 \text{ mod } n$$
By the Law of Quadratic Reciprocity
$$\left( \frac{2}{n} \right) \equiv (-1)^\frac{n^2-1}{8}\equiv (-1)^{\frac{(4p^k)(4p^k+2)}{8}}\equiv (-1)^{(p^k)(2*p^k+1)}=-1 $$
Additionally,
$$\left( \frac{3}{n} \right) =-1 $$ since by the Law of Quadratic Reciprocity,
$$\left( \frac{3}{n} \right)\left( \frac{n}{3} \right) =(-1)^{\frac{n-1}{2}\frac{3-1}{2}} = (-1)^{2*p^k}=1$$ and
$p \text{ mod } 3 \equiv 1,2$
$p^k \text{ mod } 3 \equiv 1,2$
$n \equiv 4p^k+1 \text{ mod } 3 \equiv 2,0$
Since $2$ is a quadratic nonresidue mod $3$, and n is defined as a prime greater than or equal to 5, then n cannot be a multiple of 3. Therefore,
$$\left( \frac{n}{3} \right)=-1$$
Since the Legendre Function is multiplicative, we get
$$\left( \frac{6}{n} \right)=\left( \frac{3}{n} \right)\left( \frac{2}{n} \right)=1$$, and so 6 is a quadratic residue mod n. This implies that it is possible for the number 4 to be reached again in a sequence like that. From there however, I can't seem to find any literature on how to continue, other than references to the Pisano Period (which has a derivation referring to algebraic number theory) and a closed-form for the recursion $r_k=r_{k-1}^2-2$ in the page for "Proof of correctness" in the Wikipedia page for the Lucas Lehmer primality test, which introduces the same recursion.
