Primality of the numbers in the form of $2n^2-1$

Solution 1:

Let $n=ak+b$, as you have it. Suppose prime $p|a$ and $2b^2\equiv 1\pmod{p}$. Then $2n^2-1=2(ak+b)^2-1=a(2ak^2+4abk)+2b^2-1\equiv 0\pmod{p}$, so $p|2n^2-1$ and hence $2n^2-1$ is composite.

We can test if $2b^2\equiv 1$ using Legendre symbols. Such a $b$ exists (in fact two exist) if $\left(\frac{1/2}{p}\right)=1$. We multiply both sides by $\left(\frac{2}{p}\right)$ to get $1=\left(\frac{1}{p}\right)=\left(\frac{2}{p}\right)$. This has solutions if $p\equiv 1,7\pmod{8}$.

Example: Let $a=51=3\times 17$. Since $17\equiv 1\pmod{8}$, there are two choices for $b$ such that $2b^2\equiv 1\pmod{17}$, namely $3,14$. Hence $n=51k+3$ and $n=51k+14$ will always be composite for all $k$.

Solution 2:

Take any $a$ and consider $n_a=a\pmod{2a^2-1}.$ Then $2n_a^2-1=2a^2-1\pmod{2a^2-1}$ and you get that $2n_a^2-1$ is divisible by $2a^2-1.$ Latter leads to the conclusion that all numbers of the form $2n_a^2-1$ with $n_a>a$ are composite. As to the whether there exists infinitely many primes of the form $2n^2-1,$ I believe it is an open problem.

Solution 3:

$2n^2-1\leftarrow$ Looks like Mersenne Primes. You can have numbers $n$ of form $2^k$ such that $2k+1$ is not a prime.

$2(2)^{2k}-1=2^{2k+1}-1 \implies 2k+1=mj$, you have $2n^2=(2^m)^j-1=(2^m-1)(2^{n-1}+2^{n-2}+ \dots 1) $, so, you need such $k$, which makes $2k+1$ composite.

When you have prime of the form $2k+1$, you have a Mersenne prime(Not always true).