# Conjectured compositeness tests for $N=b^n \pm b \pm 1$

How to prove that these conjectures are true?

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

Conjecture 1: Let $N= b^n-b-1$ such that $n>2$, $b \equiv 0,6 \pmod{8}$. Let $S_i=P_b(S_{i-1})$ with $S_0=P_{b/2}(6)$, thus if $N$ is prime, then $S_{n-1} \equiv P_{(b+2)/2}(6) \pmod{N}$.

Conjecture 2: Let $N= b^n-b-1$ such that $n>2$, $b \equiv 2,4 \pmod{8}$. Let $S_i=P_b(S_{i-1})$ with $S_0=P_{b/2}(6)$, thus if $N$ is prime, then $S_{n-1} \equiv -P_{b/2}(6) \pmod{N}$.

Conjecture 3: Let $N= b^n+b+1$ such that $n>2$, $b \equiv 0,6 \pmod{8}$. Let $S_i=P_b(S_{i-1})$ with $S_0=P_{b/2}(6)$, thus if $N$ is prime, then $S_{n-1} \equiv P_{b/2}(6) \pmod{N}$.

Conjecture 4: Let $N= b^n+b+1$ such that $n>2$, $b \equiv 2,4 \pmod{8}$. Let $S_i=P_b(S_{i-1})$ with $S_0=P_{b/2}(6)$, thus if $N$ is prime, then $S_{n-1} \equiv -P_{(b+2)/2}(6) \pmod{N}$.

Conjecture 5: Let $N= b^n-b+1$ such that $n>3$, $b \equiv 0,2 \pmod{8}$. Let $S_i=P_b(S_{i-1})$ with $S_0=P_{b/2}(6)$, thus if $N$ is prime, then $S_{n-1} \equiv P_{b/2}(6) \pmod{N}$.

Conjecture 6: Let $N=b^n-b+1$ such that $n>3$, $b \equiv 4,6 \pmod{8}$. Let $S_i=P_b(S_{i-1})$ with $S_0=P_{b/2}(6)$, thus if $N$ is prime, then $S_{n-1} \equiv -P_{(b-2)/2}(6) \pmod{N}$.

Conjecture 7: Let $N= b^n+b-1$ such that $n>3$, $b \equiv 0,2 \pmod{8}$. Let $S_i=P_b(S_{i-1})$ with $S_0=P_{b/2}(6)$, thus if $N$ is prime, then $S_{n-1} \equiv P_{(b-2)/2}(6) \pmod{N}$.

Conjecture 8: Let $N= b^n+b-1$ such that $n>3$, $b \equiv 4,6 \pmod{8}$. Let $S_i=P_b(S_{i-1})$ with $S_0=P_{b/2}(6)$, thus if $N$ is prime, then $S_{n-1} \equiv -P_{b/2}(6) \pmod{N}$.

Any hint is appreciated.

#### Solutions Collecting From Web of "Conjectured compositeness tests for $N=b^n \pm b \pm 1$"

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

Now, we can prove by induction that
$$S_i=p^{b^{i+1}}+q^{b^{i+1}}.$$

By the way,
\begin{align}p^{N+1}+q^{N+1}&=\sum_{i=0}^{N+1}\binom{N+1}{i}(\sqrt 2)^{i}\left((-1)^{N+1-i}+1\right)\\&=\sum_{j=0}^{(N+1)/2}\binom{N+1}{2j}2^{j+1}\\&\equiv 2+2^{(N+3)/2}\pmod N\\&\equiv 2+4\cdot 2^{\frac{N-1}{2}}\pmod N\tag1\end{align}
Also,
\begin{align}p^{N+3}+q^{N+3}&=\sum_{i=0}^{N+3}\binom{N+3}{i}(\sqrt 2)^{i}\left((-1)^{N+3-i}+1\right)\\&=\sum_{j=0}^{(N+3)/2}\binom{N+3}{2j}2^{j+1}\\&\equiv 2+\binom{N+3}{2}\cdot 2^2+\binom{N+3}{N+1}\cdot 2^{\frac{N+3}{2}}+2^{\frac{N+5}{2}}\pmod N\\&\equiv 14+12\cdot 2^{\frac{N-1}{2}}+8\cdot 2^{\frac{N-1}{2}}\pmod N\tag2\end{align}

Here, 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 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 that
$$p^{N+2i-1}+q^{N+2i-1}\equiv -\left(p^{2i-2}+q^{2i-2}\right)\pmod N\tag 4$$

To prove $(3)(4)$, we can use
$$p^{N+2(i+1)-1}+q^{N+2(i+1)-1}\equiv \left(p^{N+2i-1}+q^{N+2i-1}\right)\left(p^2+q^2\right)-\left(p^{N+2(i-1)-1}+q^{N+2(i-1)-1}\right)\pmod N$$and $$p^{N+2(i-1)-1}+q^{N+2(i-1)-1}\equiv \left(p^{N+2i-1}+q^{N+2i-1}\right)\left(p^{-2}+q^{-2}\right)-\left(p^{N+2(i+1)-1}+q^{N+2(i+1)-1}\right)\pmod N$$

(Note that $(3)(4)$ holds for every integer $i$ (not necessarily positive) because of $pq=1$.)

Conjecture 1 is true because from (3) \begin{align}S_{n-1}&=p^{N+b+1}+q^{N+b+1}\\&\equiv p^{b+2}+q^{b+2}\pmod N\\&\equiv P_{(b+2)/2}(6)\pmod N\end{align} Conjecture 2 is true because from(4)\begin{align}S_{n-1}&=p^{N+b+1}+q^{N+b+1}\\&\equiv -\left(p^{b}+q^{b}\right)\pmod N\\&\equiv -P_{b/2}(6)\pmod N\end{align} Conjecture 3 is true because from(3) \begin{align}S_{n-1}&=p^{N-b-1}+q^{N-b-1}\\&\equiv p^{-b}+q^{-b}\pmod N\\&\equiv q^b+p^b\pmod N\\&\equiv P_{b/2}(6)\pmod N\end{align}

Conjecture 4 is true because from $(4)$ \begin{align}S_{n-1}&=p^{N-b-1}+q^{N-b-1}\\&\equiv -\left(p^{-b-2}+q^{-b-2}\right)\pmod N\\&\equiv -\left(q^{b+2}+p^{b+2}\right)\pmod N\\&\equiv -P_{(b+2)/2}(6)\pmod N\end{align}

Conjecture 5 is true because from (3) \begin{align}S_{n-1}&=p^{N+b-1}+q^{N+b-1}\\&\equiv p^{b}+q^{b}\pmod N\\&\equiv P_{b/2}(6)\pmod N\end{align} Conjecture 6 is true because from(4)\begin{align}S_{n-1}&=p^{N+b-1}+q^{N+b-1}\\&\equiv -\left(p^{b-2}+q^{b-2}\right)\pmod N\\&\equiv -P_{(b-2)/2}(6)\pmod N\end{align} Conjecture 7 is true because from(3) \begin{align}S_{n-1}&=p^{N-b+1}+q^{N-b+1}\\&\equiv p^{-b+2}+q^{-b+2}\pmod N\\&\equiv q^{b-2}+p^{b-2}\pmod N\\&\equiv P_{(b-2)/2}(6)\pmod N\end{align}

Conjecture 8 is true because from $(4)$ \begin{align}S_{n-1}&=p^{N-b+1}+q^{N-b+1}\\&\equiv -\left(p^{-b}+q^{-b}\right)\pmod N\\&\equiv -\left(q^b+p^b\right)\pmod N\\&\equiv -P_{b/2}(6)\pmod N\end{align}