Can you provide proofs or counterexamples for the following two claims:
First claim
Let $P_m(x)=2^{-m}\cdot \left(\left(x-\sqrt{x^2-4}\right)^{m}+\left(x+\sqrt{x^2-4}\right)^{m}\right)$ .
Let $N_p(b)=\frac{b^p+1}{b+1}$ , where $p$ is an odd prime and $b$ is an odd natural number greater than one .
CASE(1). $b \equiv 1,9 \pmod{12}$ , or $b \equiv 3,7 \pmod{12}$ and $p \equiv 1 \pmod 4$ , or $b\equiv 5 \pmod{12}$ and $p \equiv 1,7 \pmod{12}$ , or $b \equiv 11 \pmod{12}$ and $p \equiv 1,11 \pmod{12}$ .
CASE(2). $b \equiv 3,7 \pmod{12}$ and $p \equiv 3 \pmod 4$ , or $ b\equiv 5 \pmod{12}$ and $p \equiv 5,11 \pmod{12}$ , or $b \equiv 11 \pmod{12}$ and $p \equiv 5,7 \pmod{12}$ .
Let $S_i=P_b(S_{i-1})$ with $S_0=P_b(4)$ . Suppose $N_p(b)$ is prime , then :
$\bullet$ $S_{p-1} \equiv P_{b}(4) \pmod {N_p(b)}$ if Case(1) holds ;
$\bullet$ $S_{p-1} \equiv P_{b+2}(4) \pmod {N_p(b)}$ if Case(2) holds ;
You can run this test here .
Second claim
Let $P_m(x)=2^{-m}\cdot \left(\left(x-\sqrt{x^2-4}\right)^{m}+\left(x+\sqrt{x^2-4}\right)^{m}\right)$ .
Let $M_p(a)=\frac{a^p-1}{a-1}$ , where $p$ is an odd prime and $a$ is an odd natural number greater than one .
CASE(1). $a \equiv 3,11 \pmod{12}$ , or $a \equiv 5,9 \pmod{12}$ and $p \equiv 1 \pmod 4$ , or $a\equiv 7 \pmod{12}$ and $p \equiv 1,7 \pmod{12}$ , or $a \equiv 1 \pmod{12}$ and $p \equiv 1,11 \pmod{12}$ .
CASE(2). $a \equiv 5,9 \pmod{12}$ and $p \equiv 3 \pmod 4$ , or $ a\equiv 7 \pmod{12}$ and $p \equiv 5,11 \pmod{12}$ , or $a \equiv 1 \pmod{12}$ and $p \equiv 5,7 \pmod{12}$ .
Let $S_i=P_a(S_{i-1})$ with $S_0=P_a(4)$ . Suppose $M_p(a)$ is prime , then :
$\bullet$ $S_{p-1} \equiv P_{a}(4) \pmod {M_p(a)}$ if Case(1) holds ;
$\bullet$ $S_{p-1} \equiv P_{a-2}(4) \pmod {M_p(a)}$ if Case(2) holds ;
You can run this test here .
I have tested these claims for many random values from this list .
EDIT
A command line program that implements these two tests can be found here .
The two claims are true.
Let us first prove by induction that $$S_i=\alpha^{b^{i+1}}+\beta^{b^{i+1}}\tag1$$ where $\alpha=2-\sqrt 3,\beta=2+\sqrt 3$ with $\alpha\beta=1$.
$(1)$ holds for $i=0$ since $$S_0=P_b(4)=2^{-b}\left((4-2\sqrt 3)^b+(4+2\sqrt 3)^b\right)=\alpha^{b}+\beta^{b}$$
Supposing that $(1)$ holds for some $i$ gives
$$\small\begin{align}S_{i+1}&=P_b(S_i) \\&=2^{-b}\cdot \left(\left(\alpha^{b^{i+1}}+\beta^{b^{i+1}}-\sqrt{\left(\alpha^{b^{i+1}}+\beta^{b^{i+1}}\right)^2-4}\right)^{b}+\left(\alpha^{b^{i+1}}+\beta^{b^{i+1}}+\sqrt{\left(\alpha^{b^{i+1}}+\beta^{b^{i+1}}\right)^2-4}\right)^{b}\right) \\&=2^{-b}\cdot \left(\left(\alpha^{b^{i+1}}+\beta^{b^{i+1}}-\sqrt{\left(\beta^{b^{i+1}}-\alpha^{b^{i+1}}\right)^2}\right)^{b}+\left(\alpha^{b^{i+1}}+\beta^{b^{i+1}}+\sqrt{\left(\beta^{b^{i+1}}-\alpha^{b^{i+1}}\right)^2}\right)^{b}\right) \\&=2^{-b}\cdot \left(\left(\alpha^{b^{i+1}}+\beta^{b^{i+1}}-\left(\beta^{b^{i+1}}-\alpha^{b^{i+1}}\right)\right)^{b}+\left(\alpha^{b^{i+1}}+\beta^{b^{i+1}}+\left(\beta^{b^{i+1}}-\alpha^{b^{i+1}}\right)\right)^{b}\right) \\&=\alpha^{b^{i+2}}+\beta^{b^{i+2}}\qquad\blacksquare\end{align}$$
For the first claim, let $N:=N_p(b)=\frac{b^p+1}{b+1}$.
Then, we have, from $(1)$,
$$\small\begin{align}S_{p-1} &=\alpha^{b^{p}}+\beta^{b^{p}}=\alpha^{N(b+1)-1}+\beta^{N(b+1)-1}=\alpha\beta\left(\alpha^{N(b+1)-1}+\beta^{N(b+1)-1}\right)=\beta(\alpha^{N})^{b+1}+\alpha(\beta^{N})^{b+1} \\&=\beta\left(\sum_{i=0}^{N}\binom Ni2^{N-i}(-\sqrt 3)^i\right)^{b+1} +\alpha\left(\sum_{i=0}^{N}\binom Ni2^{N-i}(\sqrt 3)^i\right)^{b+1}\end{align}$$
Here, there are integers $A,B$ divisible by $N$ such that
$\small\begin{align}S_{p-1}&=\beta\left(2^{N}+A-\sqrt 3\ \left(B+3^{(N-1)/2}\right)\right)^{b+1}+\alpha\left(2^N+A+\sqrt 3\ \left(B+3^{(N-1)/2}\right)\right)^{b+1} \\\\&=2\left(\left(2^{N}+A-\sqrt 3\ \left(B+3^{(N-1)/2}\right)\right)^{b+1}+\left(2^{N}+A+\sqrt 3\ \left(B+3^{(N-1)/2}\right)\right)^{b+1}\right) \\&\qquad +\sqrt 3\ \left(\left(2^{N}+A-\sqrt 3\ \left(B+3^{(N-1)/2}\right)\right)^{b+1}-\left(2^{N}+A+\sqrt 3\ \left(B+3^{(N-1)/2}\right)\right)^{b+1}\right) \\\\&=2\sum_{i=0}^{b+1}\binom {b+1}i(2^N+A)^{b+1-i}\left(\left(-\sqrt 3\ \left(B+3^{(N-1)/2}\right)\right)^i+\left(\sqrt 3\ \left(B+3^{(N-1)/2}\right)\right)^i\right) \\&\qquad +\sqrt 3\ \sum_{i=0}^{b+1}\binom {b+1}i(2^N+A)^{b+1-i}\left(\left(-\sqrt 3\ \left(B+3^{(N-1)/2}\right)\right)^i-\left(\sqrt 3\ \left(B+3^{(N-1)/2}\right)\right)^i\right) \\\\&=2\sum_{j=0}^{(b+1)/2}\binom {b+1}{2j}(2^N+A)^{b+1-2j}\cdot 2\left(\sqrt 3\ \left(B+3^{(N-1)/2}\right)\right)^{2j} \\&\qquad -\sqrt 3\ \sum_{j=1}^{(b+1)/2}\binom {b+1}{2j-1}(2^N+A)^{b+1-(2j-1)}\cdot 2\left(\sqrt 3\ \left(B+3^{(N-1)/2}\right)\right)^{2j-1} \\\\&=4\sum_{j=0}^{(b+1)/2}\binom {b+1}{2j}(2^N+A)^{b+1-2j}\cdot 3^j\left(B+3^{(N-1)/2}\right)^{2j} \\&\qquad -2\sum_{j=1}^{(b+1)/2}\binom {b+1}{2j-1}(2^N+A)^{b+1-(2j-1)}\cdot 3^j\left(B+3^{(N-1)/2}\right)^{2j-1} \\\\&\equiv 4\sum_{j=0}^{(b+1)/2}\binom {b+1}{2j}(2^N)^{b+1-2j}\cdot 3^j\left(3^{(N-1)/2}\right)^{2j} \\&\qquad -2\sum_{j=1}^{(b+1)/2}\binom {b+1}{2j-1}(2^N)^{b+1-(2j-1)}\cdot 3^j\left(3^{(N-1)/2}\right)^{2j-1}\pmod N \\\\&\equiv 4\sum_{j=0}^{(b+1)/2}\binom {b+1}{2j}\cdot 2^{b+1-2j}\cdot 3^j -2\cdot \color{red}{3^{(N-1)/2}}\sum_{j=1}^{(b+1)/2}\binom {b+1}{2j-1}\cdot 2^{b+1-(2j-1)}\cdot 3^j\pmod N\qquad\qquad(2)\end{align}$
Now, we have that
$\small\begin{align}P_b(4)&=\alpha^b+\beta^b=\alpha\beta(\alpha^b+\beta^b)=\beta\alpha^{b+1}+\alpha\beta^{b+1} \\&=2\left((2-\sqrt 3)^{b+1}+(2+\sqrt 3)^{b+1}\right)+\sqrt 3\ \left((2-\sqrt 3)^{b+1}-(2+\sqrt 3)^{b+1}\right) \\&=2\sum_{i=0}^{b+1}\binom{b+1}{i}2^{b+1-i}((-\sqrt 3)^i+(\sqrt 3)^i) +\sqrt 3\sum_{i=0}^{b+1}\binom{b+1}{i}2^{b+1-i}((-\sqrt 3)^i-(\sqrt 3)^i) \\&=2\sum_{j=0}^{(b+1)/2}\binom{b+1}{2j}2^{b+1-2j}\cdot 2(\sqrt 3)^{2j} -\sqrt 3\ \sum_{j=1}^{(b+1)/2}\binom{b+1}{2j-1}2^{b+1-(2j-1)}\cdot 2(\sqrt 3)^{2j-1} \\&=4\sum_{j=0}^{(b+1)/2}\binom{b+1}{2j}2^{b+1-2j}\cdot 3^j -2\cdot \color{red}1\sum_{j=1}^{(b+1)/2}\binom{b+1}{2j-1}2^{b+1-(2j-1)}\cdot 3^j\qquad\qquad\qquad\qquad\qquad\qquad (3)\end{align}$
and that
$\small\begin{align}P_{b+2}(4)&=\alpha^{b+2}+\beta^{b+2}=\alpha\cdot \alpha^{b+1}+\beta\cdot\beta^{b+1} \\&=2\left((2-\sqrt 3)^{b+1}+(2+\sqrt 3)^{b+1}\right)-\sqrt 3\ \left((2-\sqrt 3)^{b+1}-(2+\sqrt 3)^{b+1}\right) \\&=4\sum_{j=0}^{(b+1)/2}\binom{b+1}{2j}2^{b+1-2j}\cdot 3^j-2\cdot \color{red}{(-1)}\sum_{j=1}^{(b+1)/2}\binom{b+1}{2j-1}2^{b+1-(2j-1)}\cdot 3^j\qquad\qquad\qquad\qquad\qquad (4)\end{align}$
It follows from $(2)(3)(4)$ that
if $3^{(N-1)/2}\equiv 1\pmod N$, then $S_{p-1}\equiv P_b(4)\pmod N$
if $3^{(N-1)/2}\equiv -1\pmod N$, then $S_{p-1}\equiv P_{b+2}(4)\pmod N$
Now, since $$\small N=b^{p-1}-b^{p-2}+\cdots -b+1\equiv\begin{cases}1&\text{if $b\equiv 0,1\pmod 3$}\\\\1&\text{if $b\equiv 2,p\equiv 1\pmod 3$}\\\\2&\text{if $b\equiv 2,p\equiv 2\pmod 3$}\end{cases} \equiv\begin{cases}1&\text{if $b\equiv 1\pmod 4$}\\\\1&\text{if $b\equiv 3,p\equiv 1\pmod 4$}\\\\3&\text{if $b\equiv 3,p\equiv 3\pmod 4$}\end{cases}$$ we have
If $b \equiv 1,9 \pmod{12}$, then $3^{(N-1)/2}=\frac{(-1)^{(N-1)/2}}{\left(\frac N3\right)}=\frac{1}{1}=1$
If $b \equiv 3,7 \pmod{12}$ and $p \equiv 1 \pmod 4$, then $3^{(N-1)/2}=\frac{(-1)^{(N-1)/2}}{\left(\frac N3\right)}=\frac{1}{1}=1$
If $b\equiv 5 \pmod{12}$ and $p \equiv 1,7 \pmod{12}$, then $3^{(N-1)/2}=\frac{(-1)^{(N-1)/2}}{\left(\frac N3\right)}=\frac{1}{1}=1$
If $b \equiv 11 \pmod{12}$ and $p \equiv 1,11 \pmod{12}$, then $3^{(N-1)/2}=\frac{(-1)^{(N-1)/2}}{\left(\frac N3\right)}=\frac{\pm 1}{\pm 1}=1$
If $b \equiv 3,7 \pmod{12}$ and $p \equiv 3 \pmod 4$, then $3^{(N-1)/2}=\frac{(-1)^{(N-1)/2}}{\left(\frac N3\right)}=\frac{-1}{1}=-1$
If $ b\equiv 5 \pmod{12}$ and $p \equiv 5,11 \pmod{12}$, then $3^{(N-1)/2}=\frac{(-1)^{(N-1)/2}}{\left(\frac N3\right)}=\frac{1}{-1}=-1$
If $b \equiv 11 \pmod{12}$ and $p \equiv 5,7 \pmod{12}$, then $3^{(N-1)/2}=\frac{(-1)^{(N-1)/2}}{\left(\frac N3\right)}=\frac{\mp 1}{\pm 1}=-1$
Since $3^{(N-1)/2}=1$ holds in CASE(1), $S_{p-1}\equiv P_b(4)\pmod{N_p(b)}$ holds in CASE(1).
Since $3^{(N-1)/2}=-1$ holds in CASE(2), $S_{p-1}\equiv P_{b+2}(4)\pmod{N_p(b)}$ holds in CASE(2).
For the second claim, let $M:=M_p(a)=\frac{a^p-1}{a-1}$.
Then, similarly as above, we have, from $(1)$,
$$\small\begin{align}S_{p-1}&=\alpha^{a^p}+\beta^{a^p}=\alpha^{M(a-1)+1}+\beta^{M(a-1)+1}=\alpha(\alpha^M)^{a-1}+\beta(\beta^M)^{a-1} \\\\&\equiv 4\sum_{j=0}^{(a-1)/2}\binom {b+1}{2j}\cdot 2^{a-1-2j}\cdot 3^j \\&\qquad +2\cdot \color{red}{3^{(M-1)/2}}\sum_{j=1}^{(a-1)/2}\binom {a-1}{2j-1}\cdot 2^{a-1-(2j-1)}\cdot 3^j\pmod M\tag5\end{align}$$
Now, we have that $$P_a(4)=4\sum_{j=0}^{(a+1)/2}\binom{a+1}{2j}2^{a+1-2j}\cdot 3^j+2\cdot \color{red}1\sum_{j=1}^{(a+1)/2}\binom{a+1}{2j-1}\cdot 2^{a+1-(2j-1)}\cdot 3^j\tag6$$ and that $$P_{a-2}(4)=4\sum_{j=0}^{(a-1)/2}\binom{b+1}{2j}2^{a-1-2j}\cdot 3^j+2\cdot \color{red}{(-1)}\sum_{j=1}^{(a-1)/2}\binom{a-1}{2j-1}\cdot 2^{a-1-(2j-1)}\cdot 3^j\tag7$$
It follows $(5)(6)(7)$ that
if $3^{(M-1)/2}\equiv 1\pmod M$, then $S_{p-1}\equiv P_a(4)\pmod{M}$
if $3^{(M-1)/2}\equiv -1\pmod M$, then $S_{p-1}\equiv P_{a-2}(4)\pmod{M}$
Now since $$\small M=a^{p-1}+a^{p-2}+\cdots +a+1\equiv\begin{cases}1&\text{if $a\equiv 0,2\pmod 3$}\\\\1&\text{if $a\equiv 1,p\equiv 1\pmod 3$}\\\\2&\text{if $a\equiv 1,p\equiv 2\pmod 3$}\end{cases}\equiv\begin{cases}1&\text{if $a\equiv 1,p\equiv 1\pmod 4$}\\\\3&\text{if $a\equiv 1,p\equiv 3\pmod 4$}\\\\1&\text{if $a\equiv 3\pmod 4$}\end{cases}$$ we have
If $a \equiv 3,11 \pmod{12}$, then $3^{(M-1)/2}=\frac{(-1)^{(M-1)/2}}{\left(\frac M3\right)}=\frac{1}{1}=1$
If $a \equiv 5,9 \pmod{12}$ and $p \equiv 1 \pmod 4$, then $3^{(M-1)/2}=\frac{(-1)^{(M-1)/2}}{\left(\frac M3\right)}=\frac{1}{1}=1$
If $a\equiv 7 \pmod{12}$ and $p \equiv 1,7 \pmod{12}$, then $3^{(M-1)/2}=\frac{(-1)^{(M-1)/2}}{\left(\frac M3\right)}=\frac{1}{1}=1$
If $a \equiv 1 \pmod{12}$ and $p \equiv 1,11 \pmod{12}$, then $3^{(M-1)/2}=\frac{(-1)^{(M-1)/2}}{\left(\frac M3\right)}=\frac{\pm 1}{\pm 1}=1$
If $a \equiv 5,9 \pmod{12}$ and $p \equiv 3 \pmod 4$, then $3^{(M-1)/2}=\frac{(-1)^{(M-1)/2}}{\left(\frac M3\right)}=\frac{-1}{1}=-1$
If $a\equiv 7 \pmod{12}$ and $p \equiv 5,11 \pmod{12}$, then $3^{(M-1)/2}=\frac{(-1)^{(M-1)/2}}{\left(\frac M3\right)}=\frac{1}{-1}=-1$
If $a \equiv 1 \pmod{12}$ and $p \equiv 5,7 \pmod{12}$, then $3^{(M-1)/2}=\frac{(-1)^{(M-1)/2}}{\left(\frac M3\right)}=\frac{\mp 1}{\pm 1}=-1$
Since $3^{(M-1)/2}=1$ holds in CASE(1), $S_{p-1}\equiv P_{a}(4)\pmod{M_p(b)}$ holds in CASE(1).
Since $3^{(M-1)/2}=-1$ holds in CASE(2), $S_{p-1}\equiv P_{a-2}(4)\pmod{M_p(b)}$ holds in CASE(2).