<s>[INST] Primality test for $\frac{(10 \cdot 2^n)^m-1}{10 \cdot 2^n-1} - 2$ and $\frac{(10 \cdot 2^n)^m+1}{10 \cdot 2^n+1} - 2$ Here is what I observed:
For $\frac{(10 \cdot 2^n)^m-1}{10 \cdot 2^n-1} - 2$ :
Let $N$ = $\frac{(10 \cdot 2^n)^m-1}{10 \cdot 2^n-1} - 2$ :
when $m$ is a number $m \ge 3$ and $n \ge 0$.
Let the sequence $S_i=2 \cdot T_{10 \cdot 2^n}(S_{i-1}/2)$ where $T_{n}(x)$ is the Chebyshev's polynomial of the first kind with $S_0=L_{10 \cdot 2^n}$ where $L_{n}$ is the $n_{th}$ Lucas number. Then $N$ is prime if and only if $S_{m-1} \equiv L_{30 \cdot 2^n-2}\pmod{N}$.
You can run this test here.
For $\frac{(10 \cdot 2^n)^m+1}{10 \cdot 2^n+1} - 2$ :
Let $N$ = $\frac{(10 \cdot 2^n)^m+1}{10 \cdot 2^n+1} - 2$ :
when $m$ is a odd number $m \ge 3$ and $n \ge 0$.
Let the sequence $S_i=2 \cdot T_{10 \cdot 2^n}(S_{i-1}/2)$ where $T_{n}(x)$ is the Chebyshev's polynomial of the first kind with $S_0=L_{10 \cdot 2^n}$ where $L_{n}$ is the $n_{th}$ Lucas number. Then $N$ is prime if and only if $S_{m-1} \equiv L_{30 \cdot 2^n+2}\pmod{N}$.
You can run this test here.
Is there a way to explain this? I don't know how to start for proving it. If you found a counterexample please tell me.
 [/INST] It's often the case with such tests that the "only if" part is more or less easy to prove, while the "if" part is inaccessible for proving or disproving. Below I prove the "only if" part, ie. assuming that $N$ is prime.
First notice that Chebyshev polynomials appear here just for efficient computation of Lucas number
$$S_{m-1} = L_{(10\cdot 2^n)^m}.$$
Since $N\equiv -1\pmod{10}$, we have that the period of $L_k$ modulo $N$ divides $N-1$. It remains to notice that
$$(10\cdot 2^n)^m\ =\ (N+2)(10\cdot 2^n\mp 1)\pm 1\ \equiv\ 30\cdot 2^n\mp 2\pmod{N-1},$$
implying that $S_{m-1} = L_{(10\cdot 2^n)^m} \equiv L_{30\cdot 2^n\mp 2}\pmod{N}$.

PS. As for the "if" part - since its conclusion is based on a single congruence, we get an analog of Lucas preudoprimality test, which is known to have false positives. However, here we are restricted to exponentially growing numbers, where finding false positives becomes much harder if feasible.
</s>