# Compositeness tests for numbers of the form $k \cdot b^n \pm c$

Can you provide proofs or counterexamples for the following claims?

Claim 1

Let $$P_m(x)=2^{-m}\cdot((x-\sqrt{x^2-4})^m+(x+\sqrt{x^2-4})^m)$$ . Let $$M= k \cdot b^{n}-c$$ where $$k,b,n,c$$ are natural numbers such that $$k>0$$ , $$b>1$$ , $$n>1$$ and $$c>0$$. Let $$a$$ be a natural number greater than two such that $$\left(\frac{a-2}{M}\right)=-1$$ and $$\left(\frac{a+2}{M}\right)=1$$ where $$\left(\frac{}{}\right)$$ denotes Jacobi symbol. Let $$S_i=P_b(S_{i-1})$$ with $$S_0$$ equal to the modular $$P_{kb}(a)\phantom{5} \text{mod} \phantom{5} M$$. Then, if $$M$$ is prime then $$S_{n-1} \equiv P_{c-1}(a) \pmod{M}$$ .

You can run this test here .

Claim 2

Let $$P_m(x)=2^{-m}\cdot((x-\sqrt{x^2-4})^m+(x+\sqrt{x^2-4})^m)$$ . Let $$N= k \cdot b^{n}+c$$ where $$k,b,n,c$$ are natural numbers such that $$k>0$$ , $$b>1$$ , $$n>1$$ and $$c>0$$ . Let $$a$$ be a natural number greater than two such that $$\left(\frac{a-2}{N}\right)=1$$ and $$\left(\frac{a+2}{N}\right)=1$$ where $$\left(\frac{}{}\right)$$ denotes Jacobi symbol. Let $$S_i=P_b(S_{i-1})$$ with $$S_0$$ equal to the modular $$P_{kb}(a)\phantom{5} \text{mod} \phantom{5} N$$. Then, if $$N$$ is prime then $$S_{n-1} \equiv P_{c-1}(a) \pmod{N}$$ .

You can run this test here .

I have tested these claims for many random values of $$k$$ , $$b$$ , $$n$$ and $$c$$ and there were no counterexamples .

• Again, after DavidSpeyer's answer 3 years ago, did you work on the order of $6-2\sqrt{3}\in \mathbb{Z}/P\mathbb{Z}[\sqrt{3}]^\times$ with $P = 2^p-1$ which is the core of the proof of the LLT for the Mersenne numbers ? If so then what finite ring and which elements are you looking at ? – reuns Oct 18 '18 at 4:20

The two claims are true.

Proof for Claim 1 :

Let us prove by induction that $$S_i\equiv 2^{-kb^{i+1}}(s^{kb^{i+1}}+t^{kb^{i+1}})\pmod M\tag1$$ where $$s:=a-\sqrt{a^2-4},t=a+\sqrt{a^2-4}$$.

$$(1)$$ holds for $$i=0$$ since $$S_0\equiv P_{kb}(a)=2^{-kb}(s^{kb}+t^{kb})\pmod M$$

Supposing that $$(1)$$ holds for $$i$$ gives \begin{align}S_{i+1}&=P_b(S_i) \\\\&\equiv P_b(2^{-kb^{i+1}}(s^{kb^{i+1}}+t^{kb^{i+1}}))\pmod M \\\\&=2^{-b}\cdot\bigg(\bigg(2^{-kb^{i+1}}(s^{kb^{i+1}}+t^{kb^{i+1}})-\sqrt{(2^{-kb^{i+1}}(s^{kb^{i+1}}+t^{kb^{i+1}}))^2-4}\bigg)^b \\&\qquad\qquad+\bigg(2^{-kb^{i+1}}(s^{kb^{i+1}}+t^{kb^{i+1}})+\sqrt{(2^{-kb^{i+1}}(s^{kb^{i+1}}+t^{kb^{i+1}}))^2-4}\bigg)^b\bigg) \\\\&=2^{-b}\cdot\bigg(\bigg(2^{-kb^{i+1}}(s^{kb^{i+1}}+t^{kb^{i+1}})-\sqrt{(2^{-kb^{i+1}}(t^{kb^{i+1}}-s^{kb^{i+1}}))^2}\bigg)^b \\&\qquad\qquad +\bigg(2^{-kb^{i+1}}(s^{kb^{i+1}}+t^{kb^{i+1}})+\sqrt{(2^{-kb^{i+1}}(t^{kb^{i+1}}-s^{kb^{i+1}}))^2}\bigg)^b\bigg) \\\\&=2^{-b}\cdot\bigg(\bigg(2^{-kb^{i+1}}(s^{kb^{i+1}}+t^{kb^{i+1}})-2^{-kb^{i+1}}(t^{kb^{i+1}}-s^{kb^{i+1}})\bigg)^b \\&\qquad\qquad+\bigg(2^{-kb^{i+1}}(s^{kb^{i+1}}+t^{kb^{i+1}})+2^{-kb^{i+1}}(t^{kb^{i+1}}-s^{kb^{i+1}})\bigg)^b\bigg) \\\\&=2^{-kb^{i+2}}(s^{kb^{i+2}}+t^{kb^{i+2}})\qquad\square\end{align}

From $$(1)$$, we get, using $$2(a\pm\sqrt{a^2-4})=(\sqrt{a+2}\pm\sqrt{a-2})^2$$, \begin{align}S_{n-1}&\equiv 2^{-(M+c)}(s^{M+c}+t^{M+c})\pmod M \\\\&=2^{-2M-2c}\bigg((\sqrt{a+2}-\sqrt{a-2})^{2M+2c} \\&\qquad\qquad\qquad +(\sqrt{a+2}+\sqrt{a-2})^{2M+2c}\bigg)\tag2\end{align}

Here, we have, by the binomial theorem, \begin{align}&(\sqrt{a+2}\pm\sqrt{a-2})^{M} \\\\&=\sum_{k=0}^{M}\binom Mk(\sqrt{a+2})^{M-k}(\pm\sqrt{a-2})^k \\\\&=\sqrt{a+2}\sum_{j=0}^{(M-1)/2}\binom{M}{2j}(a+2)^{(M-2j-1)/2}(a-2)^{j} \\&\qquad\qquad \pm\sqrt{a-2}\sum_{j=1}^{(M+1)/2}\binom{M}{2j-1}(a+2)^{(M-2j+1)/2}(a-2)^{j-1}\end{align}

So, there are integers $$C,D$$ such that $$(\sqrt{a+2}\pm\sqrt{a-2})^{M}=C\sqrt{a+2}\pm D\sqrt{a-2}$$ where $$C=\sum_{j=0}^{(M-1)/2}\binom{M}{2j}(a+2)^{(M-2j-1)/2}(a-2)^{j}\equiv \left(\frac{a+2}{M}\right)\equiv 1\pmod M$$ and $$D=\sum_{j=1}^{(M+1)/2}\binom{M}{2j-1}(a+2)^{(M-2j+1)/2}(a-2)^{j-1}\equiv \left(\frac{a-2}{M}\right)\equiv -1\pmod M$$

From $$(2)$$, we get \begin{align}2^{2(M-1)}\cdot S_{n-1}&\equiv 2^{-2c-2}\left((\sqrt{a+2}-\sqrt{a-2})^{2M+2c}+(\sqrt{a+2}+\sqrt{a-2})^{2M+2c}\right)\pmod M \\\\&=2^{-2c-2}\bigg((\sqrt{a+2}-\sqrt{a-2})^{2c}(C\sqrt{a+2}- D\sqrt{a-2})^2 \\&\qquad +(\sqrt{a+2}+\sqrt{a-2})^{2c}(C\sqrt{a+2}+ D\sqrt{a-2})^2\bigg) \\\\&\equiv 2^{-2c-2}\bigg((\sqrt{a+2}-\sqrt{a-2})^{2c}(\sqrt{a+2}+\sqrt{a-2})^2 \\&\qquad +(\sqrt{a+2}+\sqrt{a-2})^{2c}(\sqrt{a+2}-\sqrt{a-2})^2\bigg)\pmod M \\\\&=2^{-2c+2}\bigg((\sqrt{a+2}-\sqrt{a-2})^{2c-2}+(\sqrt{a+2}+\sqrt{a-2})^{2c-2}\bigg) \\\\&=2^{-(c-1)}(s^{c-1}+t^{c-1}) \\\\&=P_{c-1}(a)\end{align} It follows from $$2^{2(M-1)}\equiv 1\pmod M$$ that $$S_{n-1}\equiv P_{c-1}(a)\pmod M$$

Proof for Claim 2 :

From $$(1)$$, we get, similarly as above, \begin{align}2^{2(N-1)}\cdot S_{n-1}&\equiv 2^{N+c-2}(s^{N-c}+t^{N-c})\pmod N \\\\&=2^{2c-2}((\sqrt{s+2}-\sqrt{s-2})^{2N-2c}+(\sqrt{s+2}+\sqrt{s-2})^{2N-2c}) \\\\&=2^{2c-2}\bigg((\sqrt{s+2}-\sqrt{s-2})^{2N}\bigg(\frac{\sqrt{s+2}+\sqrt{s-2}}{4}\bigg)^{2c} \\&\qquad\qquad +(\sqrt{s+2}+\sqrt{s-2})^{2N}\bigg(\frac{\sqrt{s+2}-\sqrt{s-2}}{4}\bigg)^{2c}\bigg) \\\\&\equiv 2^{-2c-2}((\sqrt{s+2}-\sqrt{s-2})^2(\sqrt{s+2}+\sqrt{s-2})^{2c} \\&\qquad\qquad +(\sqrt{s+2}+\sqrt{s-2})^2(\sqrt{s+2}-\sqrt{s-2})^{2c})\pmod N \\\\&=2^{-2c+2}((\sqrt{s+2}+\sqrt{s-2})^{2c-2}+(\sqrt{s+2}-\sqrt{s-2})^{2c-2}) \\\\&=2^{-(c-1)}(s^{c-1}+t^{c-1}) \\\\&=P_{c-1}(a)\end{align} It follows from $$2^{2(N-1)}\equiv 1\pmod N$$ that $$S_{n-1}\equiv P_{c-1}(a)\pmod N$$