Primality criteria for specific classes of generalized Fermat numbers

318 Views Asked by At

Can you provide proofs or counterexamples for the following two claims:

First claim

Let $P_m(x)=2^{-m}\cdot((x-\sqrt{x^2-4})^m+(x+\sqrt{x^2-4})^m)$ . Let $ F_n(b)= b^{2^n}+1 $ where $b$ is an even integer , $3\nmid b$ , $b \equiv 2,4,10,12 \pmod{14}$ and $n\ge2$ . Let $S_i=P_b(S_{i-1})$ with $ S_0=P_{b/2}(P_{b/2}(5))$ , then $F_n(b)$ is prime iff $S_{2^n-2} \equiv 0 \pmod{F_n(b)}$ .

You can run this test here .

Second claim

Let $P_m(x)=2^{-m}\cdot((x-\sqrt{x^2-4})^m+(x+\sqrt{x^2-4})^m)$ . Let $F_n(b)= b^{2^n}+1 $ where $b$ is an even integer , $5\nmid b$ , $b \equiv 2,4,10,12 \pmod{14}$ and $n\ge2$ . Let $S_i=P_b(S_{i-1})$ with $ S_0=P_{b/2}(P_{b/2}(12))$ , then $F_n(b)$ is prime iff $S_{2^n-2} \equiv 0 \pmod{F_n(b)}$ .

You can run this test here .

A list of generalized Fermat primes sorted by base b can be found here .

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

1

There are 1 best solutions below

0
On

This is a partial answer.

This answer proves that the following two claims are true :

Claim A : Let $P_m(x)=2^{-m}\cdot((x-\sqrt{x^2-4})^m+(x+\sqrt{x^2-4})^m)$. Let $ F_n(b)= b^{2^n}+1 $ where $b$ is an even integer, $3\nmid b$, $b \equiv 2,4,10,12 \pmod{14}$ and $n\ge2$. Let $S_i=P_b(S_{i-1})$ with $ S_0=P_{b/2}(P_{b/2}(5))$. If $F_n(b)$ is prime, then $S_{2^n-2} \equiv 0 \pmod{F_n(b)}$.

Claim B : Let $P_m(x)=2^{-m}\cdot((x-\sqrt{x^2-4})^m+(x+\sqrt{x^2-4})^m)$. Let $F_n(b)= b^{2^n}+1 $ where $b$ is an even integer, $5\nmid b$, $b \equiv 2,4,10,12 \pmod{14}$ and $n\ge2$. Let $S_i=P_b(S_{i-1})$ with $ S_0=P_{b/2}(P_{b/2}(12))$. If $F_n(b)$ is prime, then $S_{2^n-2} \equiv 0 \pmod{F_n(b)}$.


Proof for Claim A :

First of all, let us prove by induction on $i$ that $$S_i=2^{-b^{i+2}/4}(p^{b^{i+2}/4}+q^{b^{i+2}/4})\tag1$$ where $p=5-\sqrt{21},q=5+\sqrt{21}$.

$(1)$ is true for $i=0$ since $$\small\begin{align}S_0&=P_{b/2}(P_{b/2}(5)) \\\\&=2^{-b/2}\bigg(\bigg(2^{-b/2}(p^{b/2}+q^{b/2})-\sqrt{(2^{-b/2}(p^{b/2}+q^{b/2}))^2-4}\bigg)^{b/2} \\&\qquad\qquad +\bigg(2^{-b/2}(p^{b/2}+q^{b/2})+\sqrt{(2^{-b/2}(p^{b/2}+q^{b/2}))^2-4}\bigg)^{b/2}\bigg) \\\\&=2^{-b/2}\bigg(\bigg(2^{-b/2}(p^{b/2}+q^{b/2})-\sqrt{(2^{-b/2}(q^{b/2}-p^{b/2}))^2}\bigg)^{b/2} \\&\qquad\qquad +\bigg(2^{-b/2}(p^{b/2}+q^{b/2})+\sqrt{(2^{-b/2}(q^{b/2}-p^{b/2}))^2}\bigg)^{b/2}\bigg) \\\\&=2^{-b/2}\bigg(\bigg(2^{-b/2}(p^{b/2}+q^{b/2})-2^{-b/2}(q^{b/2}-p^{b/2})\bigg)^{b/2} \\&\qquad\qquad +\bigg(2^{-b/2}(p^{b/2}+q^{b/2})+2^{-b/2}(q^{b/2}-p^{b/2})\bigg)^{b/2}\bigg) \\\\&=2^{-b^2/4}(p^{b^2/4}+q^{b^2/4})\end{align}$$

Supposing that $(1)$ is true for $i$ gives $$\begin{align}S_{i+1}&=P_b(S_{i}) \\\\&=2^{-b}\cdot\bigg(\bigg(2^{-b^{i+2}/4}(p^{b^{i+2}/4}+q^{b^{i+2}/4})-\sqrt{(2^{-b^{i+2}/4}(p^{b^{i+2}/4}+q^{b^{i+2}/4}))^2-4}\bigg)^b \\&\qquad+\bigg(2^{-b^{i+2}/4}(p^{b^{i+2}/4}+q^{b^{i+2}/4})+\sqrt{(2^{-b^{i+2}/4}(p^{b^{i+2}/4}+q^{b^{i+2}/4}))^2-4}\bigg)^b\bigg) \\\\&=2^{-b}\cdot\bigg(\bigg(2^{-b^{i+2}/4}(p^{b^{i+2}/4}+q^{b^{i+2}/4})-\sqrt{(2^{-b^{i+2}/4}(q^{b^{i+2}/4}-p^{b^{i+2}/4}))^2}\bigg)^b \\&\qquad+\bigg(2^{-b^{i+2}/4}(p^{b^{i+2}/4}+q^{b^{i+2}/4})+\sqrt{(2^{-b^{i+2}/4}(q^{b^{i+2}/4}-p^{b^{i+2}/4}))^2}\bigg)^b\bigg) \\\\&=2^{-b}\cdot\bigg(\bigg(2^{-b^{i+2}/4}(p^{b^{i+2}/4}+q^{b^{i+2}/4})-2^{-b^{i+2}/4}(q^{b^{i+2}/4}-p^{b^{i+2}/4})\bigg)^b \\&\qquad+\bigg(2^{-b^{i+2}/4}(p^{b^{i+2}/4}+q^{b^{i+2}/4})+2^{-b^{i+2}/4}(q^{b^{i+2}/4}-p^{b^{i+2}/4})\bigg)^b\bigg) \\\\&=2^{-b^{i+3}/4}(p^{b^{i+3}/4}+q^{b^{i+3}/4})\qquad\square\end{align}$$

Let $N:=F_n(b)=b^{2^n}+1$. Then, from $(1)$, we get, using $\sqrt{5\pm\sqrt{21}}=\frac 12(\sqrt{14}\pm\sqrt 6)$,

$$S_{2^n-2}=2^{-(N-1)/4}\left(\left(\frac{\sqrt{14}-\sqrt 6}{2}\right)^{(N-1)/2}+\left(\frac{\sqrt{14}+\sqrt 6}{2}\right)^{(N-1)/2}\right)$$

Multiplying the both sides by $2^{(N-1)/4}\cdot 2^{(N-1)/2}$ gives

$$2^{(N-1)/4}\cdot 2^{(N-1)/2}\cdot S_{2^n-2}=(\sqrt{14}-\sqrt 6)^{(N-1)/2}+(\sqrt{14}+\sqrt 6)^{(N-1)/2}$$

Squaring the both sides gives

$$2^{(N-1)/2}\cdot 2^{N-1}\cdot S_{2^n-2}^2=(\sqrt{14}-\sqrt 6)^{N-1}+(\sqrt{14}+\sqrt 6)^{N-1}+2\cdot 8^{(N-1)/2}$$

Subtracting $2\cdot 8^{(N-1)/2}$ from the both sides gives

$$2^{(N-1)/2}\cdot 2^{N-1}\cdot S_{2^n-2}^2-2\cdot 8^{(N-1)/2}=(\sqrt{14}-\sqrt 6)^{N-1}+(\sqrt{14}+\sqrt 6)^{N-1}$$

Multiplying the both sides by $$8=(\sqrt{14}-\sqrt 6)(\sqrt{14}+\sqrt 6)$$ gives $$\small 8\cdot 2^{(N-1)/2}\cdot 2^{N-1}\cdot S_{2^n-2}^2-8\cdot 2\cdot \left(2^{(N-1)/2}\right)^3=(\sqrt{14}+\sqrt 6)(\sqrt{14}-\sqrt 6)^{N}+(\sqrt{14}-\sqrt 6)(\sqrt{14}+\sqrt 6)^{N}\tag2$$

Now, $$\begin{align}&(\sqrt{14}+\sqrt 6)(\sqrt{14}-\sqrt 6)^{N}+(\sqrt{14}-\sqrt 6)(\sqrt{14}+\sqrt 6)^{N} \\\\&=\sqrt{14}\left(\left(\sqrt{14}-\sqrt 6\right)^{N}+\left(\sqrt{14}+\sqrt 6\right)^{N}\right)-\sqrt 6\left(\left(\sqrt{14}+\sqrt 6\right)^{N}-\left(\sqrt{14}-\sqrt 6\right)^{N}\right) \\\\&=\sqrt{14}\sum_{k=0}^{N}\binom Nk(\sqrt{14})^{N-k}((-\sqrt 6)^k+(\sqrt 6)^k)-\sqrt 6\sum_{k=0}^{N}\binom Nk(\sqrt{14})^{N-k}((\sqrt 6)^k-(-\sqrt 6)^k) \\\\&=\sum_{j=0}^{(N-1)/2}\binom N{2j}14^{(N-2j+1)/2}\cdot 2\cdot 6^j-\sum_{j=1}^{(N+1)/2}\binom N{2j-1}\cdot 14^{(N-2j+1)/2}\cdot 2\cdot 6^j \\\\&\equiv 2\cdot 2\cdot 2^{(N-1)/2}\cdot 7\cdot 7^{(N-1)/2}-2\cdot 2\cdot 2^{(N-1)/2}\cdot 3\cdot 3^{(N-1)/2}\pmod N \\\\&\equiv 2\cdot 2\cdot 2^{(N-1)/2}\cdot 7\cdot \frac{(-1)^{3(N-1)/2}}{\left(\frac N7\right)}-2\cdot 2\cdot 2^{(N-1)/2}\cdot 3\cdot \frac{(-1)^{(N-1)/2}}{\left(\frac N3\right)}\pmod N \\\\&\equiv 2\cdot 2\cdot 1\cdot 7\cdot \frac{1}{-1}-2\cdot 2\cdot 1\cdot 3\cdot \frac{1}{-1}\pmod N \\\\&\equiv -16\pmod N\end{align}$$where $\left(\frac{q}{p}\right)$ denotes the Legendre symbol.

It follows from $(2)$ that $$8S_{2^n-2}^2\equiv 0\pmod N$$ Since $\gcd(8,N)=1$, we get $$S_{2^n-2}\equiv 0\pmod{F_n(b)}\qquad\blacksquare$$


Proof for Claim B :

We can prove by induction on $i$ that $$S_i=2^{-b^{i+2}/4}(s^{b^{i+2}/4}+t^{b^{i+2}/4})\tag3$$ where $s=12-2\sqrt{35},t=12+2\sqrt{35}$ similarly as above.

Let $N:=F_n(b)=b^{2^n}+1$. Then, from $(3)$, we get, using $\sqrt{12\pm 2\sqrt{35}}=\sqrt{7}\pm\sqrt 5$,

$$S_{2^n-2}=2^{-(N-1)/4}\left((\sqrt 7-\sqrt 5)^{(N-1)/2}+(\sqrt 7+\sqrt 5)^{(N-1)/2}\right)$$

So, we get $$\small 2\cdot 2^{(N-1)/2}\cdot S_{2^n-2}^2-4\cdot 2^{(N-1)/2}=(\sqrt 7+\sqrt 5)(\sqrt 7-\sqrt 5)^N+(\sqrt 7-\sqrt 5)(\sqrt 7+\sqrt 5)^N\tag4$$

Now,$$\begin{align}&(\sqrt 7+\sqrt 5)(\sqrt 7-\sqrt 5)^N+(\sqrt 7-\sqrt 5)(\sqrt 7+\sqrt 5)^N \\\\&=\sqrt 7\left((\sqrt 7-\sqrt 5)^N+(\sqrt 7+\sqrt 5)^N\right)-\sqrt 5\left((\sqrt 7+\sqrt 5)^N-(\sqrt 7-\sqrt 5)^N\right) \\\\&=\sqrt 7\sum_{k=0}^{N}\binom Nk(\sqrt 7)^{N-k}((-\sqrt 5)^k+(\sqrt 5)^k)-\sqrt 5\sum_{k=0}^{N}\binom Nk(\sqrt 7)^{N-k}((\sqrt 5)^k-(-\sqrt 5)^k) \\\\&=\sum_{j=0}^{(N-1)/2}\binom N{2j}7^{(N-2j+1)/2}\cdot 2\cdot 5^j-\sum_{j=1}^{(N+1)/2}\binom N{2j-1}7^{(N-2j+1)/2}\cdot 2\cdot 5^j \\\\&\equiv 2\cdot 7\cdot 7^{(N-1)/2}-2\cdot 5\cdot 5^{(N-1)/2}\pmod N \\\\&\equiv 2\cdot 7\cdot \frac{(-1)^{3(N-1)/2}}{\left(\frac N7\right)}-2\cdot 5\cdot\frac{(-1)^{N-1}}{\left(\frac N5\right)}\pmod N \\\\&\equiv 2\cdot 7\cdot \frac{1}{-1}-2\cdot 5\cdot\frac{1}{-1}\pmod N \\\\&\equiv -4\pmod N\end{align}$$

It follows from $(4)$ and $2^{(N-1)/2}\equiv 1\pmod N$ that $$S_{2^n-2}\equiv 0\pmod{F_n(b)}\qquad\blacksquare$$