Conjectured compositeness tests for $N=k\cdot b^n \pm c$

Question

How to prove that these conjectures are true ?

Definition : $\text{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)~ , \text{where}~ m ~\text{and}~ x ~\text{are nonnegative integers} .$

Conjecture 1

$$\text{Let} ~N=k\cdot b^n-c ~\text{such that}~ b\equiv 0 \pmod{2}, n>bc , k>0 , c>0 ~\text{and}~ c\equiv 1,7 \pmod{8}$$

$$\text{Let}~ S_i=P_b(S_{i-1})~ \text{with}~ S_0=P_{bk/2}(P_{b/2}(6)) , ~\text{then}$$

$$\text{If}~ N ~\text{is prime then}~ S_{n-1} \equiv P_{(b/2)\cdot\lceil c/2 \rceil}(6) \pmod{N}$$

Searching for counterexample (PARI/GP)

CEkbc(b,c,g)=
{
for(k=1,9,
for(n=b*c+1,g,
N=k*b^n-c;
my(s=Mod(2*polchebyshev(k*b/2,1,polchebyshev(b/2,1,3)),N)); 
for(i=1,n-1,s=2*polchebyshev(b,1,s/2)); 
if(!(s==2*polchebyshev((b/2)*ceil(c/2),1,3)) && isprime(N),print(k,n))))
}

Conjecture 2

$$\text{Let} ~N=k\cdot b^n-c ~\text{such that}~ b\equiv 0,4,8 \pmod{12}, n>bc , k>0 , c>0 ~$$

$$\text{and}~ c\equiv 3,5 \pmod{8} .$$

$$\text{Let}~ S_i=P_b(S_{i-1})~ \text{with}~ S_0=P_{bk/2}(P_{b/2}(6)) , ~\text{then}$$

$$\text{If}~ N ~\text{is prime then}~ S_{n-1} \equiv P_{(b/2)\cdot\lfloor c/2 \rfloor}(6) \pmod{N}$$

Searching for counterexample (PARI/GP)

CEkbc(b,c,g)=
{
for(k=1,9,
for(n=b*c+1,g,
N=k*b^n-c;
my(s=Mod(2*polchebyshev(k*b/2,1,polchebyshev(b/2,1,3)),N)); 
for(i=1,n-1,s=2*polchebyshev(b,1,s/2)); 
if(!(s==2*polchebyshev((b/2)*floor(c/2),1,3)) && isprime(N),print(k,n))))
}

Conjecture 3

$$\text{Let} ~N=k\cdot b^n-c ~\text{such that}~ b\equiv 2,6,10 \pmod{12}, n>bc , k>0 , c>0 ~$$

$$\text{and}~ c\equiv 3,5 \pmod{8} .$$

$$\text{Let}~ S_i=P_b(S_{i-1})~ \text{with}~ S_0=P_{bk/2}(P_{b/2}(6)) , ~\text{then}$$

$$\text{If}~ N ~\text{is prime then}~ S_{n-1} \equiv -P_{(b/2)\cdot\lfloor c/2 \rfloor}(6) \pmod{N}$$

Searching for counterexample (PARI/GP)

CEkbc(b,c,g)=
{
for(k=1,9,
for(n=b*c+1,g,
N=k*b^n-c;
my(s=Mod(2*polchebyshev(k*b/2,1,polchebyshev(b/2,1,3)),N)); 
for(i=1,n-1,s=2*polchebyshev(b,1,s/2)); 
if(!(s==N-2*polchebyshev((b/2)*floor(c/2),1,3)) && isprime(N),print(k,n))))
}

Conjecture 4

$$\text{Let} ~N=k\cdot b^n+c ~\text{such that}~ b\equiv 0 \pmod{2}, n>bc , k>0 , c>0 ~\text{and}~ c\equiv 1,7 \pmod{8}$$

$$\text{Let}~ S_i=P_b(S_{i-1})~ \text{with}~ S_0=P_{bk/2}(P_{b/2}(6)) , ~\text{then}$$

$$\text{If}~ N ~\text{is prime then}~ S_{n-1} \equiv P_{(b/2)\cdot\lfloor c/2 \rfloor}(6) \pmod{N}$$

Searching for counterexample (PARI/GP)

CEkbc(b,c,g)=
{
for(k=1,9,
for(n=b*c+1,g,
N=k*b^n+c;
my(s=Mod(2*polchebyshev(k*b/2,1,polchebyshev(b/2,1,3)),N)); 
for(i=1,n-1,s=2*polchebyshev(b,1,s/2)); 
if(!(s==2*polchebyshev((b/2)*floor(c/2),1,3)) && isprime(N),print(k,n))))
}

Conjecture 5

$$\text{Let} ~N=k\cdot b^n+c ~\text{such that}~ b\equiv 0,4,8 \pmod{12}, n>bc , k>0 , c>0 ~$$

$$\text{and}~ c\equiv 3,5 \pmod{8} .$$

$$\text{Let}~ S_i=P_b(S_{i-1})~ \text{with}~ S_0=P_{bk/2}(P_{b/2}(6)) , ~\text{then}$$

$$\text{If}~ N ~\text{is prime then}~ S_{n-1} \equiv P_{(b/2)\cdot\lceil c/2 \rceil}(6) \pmod{N}$$

Searching for counterexample (PARI/GP)

CEkbc(b,c,g)=
{
for(k=1,9,
for(n=b*c+1,g,
N=k*b^n+c;
my(s=Mod(2*polchebyshev(k*b/2,1,polchebyshev(b/2,1,3)),N)); 
for(i=1,n-1,s=2*polchebyshev(b,1,s/2)); 
if(!(s==2*polchebyshev((b/2)*ceil(c/2),1,3)) && isprime(N),print(k,n))))
}

Conjecture 6

$$\text{Let} ~N=k\cdot b^n+c ~\text{such that}~ b\equiv 2,6,10 \pmod{12}, n>bc , k>0 , c>0 ~$$

$$\text{and}~ c\equiv 3,5 \pmod{8} .$$

$$\text{Let}~ S_i=P_b(S_{i-1})~ \text{with}~ S_0=P_{bk/2}(P_{b/2}(6)) , ~\text{then}$$

$$\text{If}~ N ~\text{is prime then}~ S_{n-1} \equiv -P_{(b/2)\cdot\lceil c/2 \rceil}(6) \pmod{N}$$

Searching for counterexample (PARI/GP)

CEkbc(b,c,g)=
{
for(k=1,9,
for(n=b*c+1,g,
N=k*b^n+c;
my(s=Mod(2*polchebyshev(k*b/2,1,polchebyshev(b/2,1,3)),N)); 
for(i=1,n-1,s=2*polchebyshev(b,1,s/2)); 
if(!(s==N-2*polchebyshev((b/2)*ceil(c/2),1,3)) && isprime(N),print(k,n))))
}

Any hint will be appreciated .

Answer 1

Your six conjectures are true.

First of all,$$\begin{align}P_{b/2}(6)&=2^{-b/2}\left(\left(6-4\sqrt{2}\right)^{b/2}+\left(6+4\sqrt{2}\right)^{b/2}\right)\\&=\left(3-2\sqrt 2\right)^{b/2}+\left(3+2\sqrt 2\right)^{b/2}\\&=p^b+q^b\end{align}$$where $p=\sqrt 2-1,q=\sqrt 2+1$ with $pq=1$.

From $$S_0=P_{bk/2}(P_{b/2}(6))=2^{-bk/2}\left(\left(2p^b\right)^{bk/2}+\left(2q^b\right)^{bk/2}\right)=p^{b^2k/2}+q^{b^2k/2}$$ and $S_i=P_b(S_{i-1})$, we can prove by induction on $i\in\mathbb N$ that $$S_i=p^{b^{i+2}k/2}+q^{b^{i+2}k/2}.$$

By the way, we have the following $(1)(2)(3)(4)$ (for the details, see this answer for your similar question): $$p^{N+1}+q^{N+1}\equiv 2+4\cdot 2^{\frac{N-1}{2}}\pmod N\tag1$$

$$p^{N+3}+q^{N+3}\equiv 14+12\cdot 2^{\frac{N-1}{2}}+8\cdot 2^{\frac{N-1}{2}}\pmod N\tag2$$

For $N\equiv\pm 1\pmod 8$, since $2^{\frac{N-1}{2}}\equiv 1\pmod N$, from $(1)(2)$, we can prove by induction on $i\in\mathbb Z$ that $$p^{N+2i-1}+q^{N+2i-1}\equiv p^{2i}+q^{2i}\pmod N\tag 3$$

For $N\equiv 3,5\pmod 8$, since $2^{\frac{N-1}{2}}\equiv -1\pmod N$, from $(1)(2)$, we can prove by induction on $i\in\mathbb Z$ that $$p^{N+2i-1}+q^{N+2i-1}\equiv -\left(p^{2i-2}+q^{2i-2}\right)\pmod N\tag 4$$

Now, for $N\equiv\pm 1\pmod 8$, from $(3)$, we can prove by induction on $j\in\mathbb N$ that $$p^{j(N+2i-1)}+q^{j(N+2i-1)}\equiv p^{2ij}+q^{2ij}\pmod N\tag 5$$

Also, for $N\equiv 3,5\pmod 8$, from $(4)$, we can prove by induction on $j\in\mathbb N$ that $$p^{j(N+2i-1)}+q^{j(N+2i-1)}\equiv (-1)^j\left(p^{j(2i-2)}+q^{j(2i-2)}\right)\pmod N\tag6$$

To prove $(5)(6)$, we can use

$$p^{(j+1)(N+2i-1)}+q^{(j+1)(N+2i-1)}\equiv \left(p^{j(N+2i-1)}+q^{j(N+2i-1)}\right)\left(p^{N+2i-1}+q^{N+2i-1}\right)-\left(p^{(j-1)(N+2i-1)}+q^{(j-1)(N+2i-1)}\right)\pmod N$$

For conjecture 1, $N\equiv \pm 1\pmod 8$ follows from the conditions $N=k\cdot b^n-c ~\text{such that}~ b\equiv 0 \pmod{2}, n>bc , k>0 , c>0 ~\text{and}~ c\equiv 1,7 \pmod{8}$. Then, we can say that conjecture 1 is true because using $(5)$ and setting $c=2d-1$ gives$$\begin{align}S_{n-1}&=p^{b^{n+1}k/2}+q^{b^{n+1}k/2}\\&=p^{(b/2)(N+c)}+q^{(b/2)(N+c)}\\&=p^{(b/2)(N+2d-1)}+q^{(b/2)(N+2d-1)}\\&\equiv p^{2\cdot d\cdot (b/2)}+q^{2\cdot d\cdot (b/2)}\pmod N\\&\equiv P_{(b/2)\cdot d}(6)\pmod N\\&\equiv P_{(b/2)\cdot \lceil c/2\rceil}(6)\pmod N\end{align}$$

For conjecture 2, $N\equiv 3,5\pmod 8$ follows from the conditions $N=k\cdot b^n-c ~\text{such that}~ b\equiv 0,4,8 \pmod{12}, n>bc , k>0 , c>0,\text{and}~ c\equiv 3,5 \pmod{8}$. Then, we can say that conjecture 2 is true because using $(6)$ and setting $c=2d-1$ gives$$\begin{align}S_{n-1}&=p^{b^{n+1}k/2}+q^{b^{n+1}k/2}\\&=p^{(b/2)(N+c)}+q^{(b/2)(N+c)}\\&=p^{(b/2)(N+2d-1)}+q^{(b/2)(N+2d-1)}\\&\equiv (-1)^{b/2}\left(p^{(b/2)\cdot (2d-2)}+q^{(b/2)\cdot (2d-2)}\right)\pmod N\\&\equiv P_{(b/2)\cdot (d-1)}(6)\pmod N\\&\equiv P_{(b/2)\cdot \lfloor c/2\rfloor}(6)\pmod N\end{align}$$

For conjecture 3, $N\equiv 3,5\pmod 8$ follows from the conditions $N=k\cdot b^n-c ~\text{such that}~ b\equiv 2,6,10 \pmod{12}, n>bc , k>0 , c>0 ~,\text{and}$ $c\equiv 3,5 \pmod{8}$. Then, we can say that conjecture 3 is true because using $(6)$ and setting $c=2d-1$ gives$$\begin{align}S_{n-1}&=p^{b^{n+1}k/2}+q^{b^{n+1}k/2}\\&=p^{(b/2)(N+c)}+q^{(b/2)(N+c)}\\&=p^{(b/2)(N+2d-1)}+q^{(b/2)(N+2d-1)}\\&\equiv (-1)^{b/2}\left(p^{(b/2)\cdot (2d-2)}+q^{(b/2)\cdot (2d-2)}\right)\pmod N\\&\equiv -P_{(b/2)\cdot (d-1)}(6)\pmod N\\&\equiv -P_{(b/2)\cdot \lfloor c/2\rfloor}(6)\pmod N\end{align}$$

For conjecture 4, $N\equiv \pm 1\pmod 8$ follows from the conditions $N=k\cdot b^n+c ~\text{such that}~ b\equiv 0 \pmod{2}, n>bc , k>0 , c>0 ~\text{and}~ c\equiv 1,7 \pmod{8}$. Then, we can say that conjecture 4 is true because using $(5)$ and setting $c=2d-1$ gives$$\begin{align}S_{n-1}&=p^{b^{n+1}k/2}+q^{b^{n+1}k/2}\\&=p^{(b/2)(N-c)}+q^{(b/2)(N-c)}\\&=p^{(b/2)(N-2d+1))}+q^{(b/2)(N-2d+1)}\\&=p^{(b/2)(N+2(-d+1)-1)}+q^{(b/2)(N+2(-d+1)-1)}\\&\equiv p^{2\cdot (-d+1)\cdot (b/2)}+q^{2\cdot (-d+1)\cdot (b/2)}\pmod N\\&\equiv q^{2\cdot (d-1)\cdot (b/2)}+p^{2\cdot (d-1)\cdot (b/2)}\pmod N\\&\equiv P_{(b/2)\cdot (d-1)}(6)\pmod N\\&\equiv P_{(b/2)\cdot \lfloor c/2\rfloor}(6)\pmod N\end{align}$$

For conjecture 5, $N\equiv 3,5\pmod 8$ follows from the conditions $N=k\cdot b^n+c ~\text{such that}~ b\equiv 0,4,8 \pmod{12}, n>bc , k>0 , c>0 ~,\text{and}~ c\equiv 3,5 \pmod{8}$. Then, we can say that conjecture 5 is true because using $(6)$ and setting $c=2d-1$ gives$$\begin{align}S_{n-1}&=p^{b^{n+1}k/2}+q^{b^{n+1}k/2}\\&=p^{(b/2)(N-c)}+q^{(b/2)(N-c)}\\&=p^{(b/2)(N-2d+1)}+q^{(b/2)(N-2d+1)}\\&=p^{(b/2)(N+2(-d+1)-1)}+q^{(b/2)(N+2(-d+1)-1)}\\&\equiv (-1)^{b/2}\left(p^{(b/2)\cdot (2(-d+1)-2)}+q^{(b/2)\cdot (2(-d+1)-2)}\right)\pmod N\\&\equiv q^{(b/2)\cdot 2d}+p^{(b/2)\cdot 2d}\pmod N\\&\equiv P_{(b/2)\cdot d}(6)\pmod N\\&\equiv P_{(b/2)\cdot \lceil c/2\rceil}(6)\pmod N\end{align}$$

For conjecture 6, $N\equiv 3,5\pmod 8$ follows from the conditions $N=k\cdot b^n+c ~\text{such that}~ b\equiv 2,6,10 \pmod{12}, n>bc , k>0 , c>0 ~,\text{and}$ $c\equiv 3,5 \pmod{8}$. Then, we can say that conjecture 6 is true because using $(6)$ and setting $c=2d-1$ gives$$\begin{align}S_{n-1}&=p^{b^{n+1}k/2}+q^{b^{n+1}k/2}\\&=p^{(b/2)(N-c)}+q^{(b/2)(N-c)}\\&=p^{(b/2)(N-2d+1)}+q^{(b/2)(N-2d+1)}\\&=p^{(b/2)(N+2(-d+1)-1)}+q^{(b/2)(N+2(-d+1)-1)}\\&\equiv (-1)^{b/2}\left(p^{(b/2)\cdot (2(-d+1)-2)}+q^{(b/2)\cdot (2(-d+1)-2)}\right)\pmod N\\&\equiv -\left(q^{(b/2)\cdot 2d}+p^{(b/2)\cdot 2d}\right)\pmod N\\&\equiv -P_{(b/2)\cdot d}(6)\pmod N\\&\equiv -P_{(b/2)\cdot \lceil c/2\rceil}(6)\pmod N\end{align}$$