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

I have a question about primality of integers in the form of $2n^2-1$.

I can prove that for the certain type of n such integers are always composite. For example, if $n=7k+2$ or $n=7k+5$, the whole expression would be always divisible by $7$.

The same is applicable to the whole (probably infinite) set of numbers in the form of $n=ak+b$, where $a$ is $7$, $17$, $23$ etc. and $b$ usually has two values (like $2$ and $5$ for $a=7$). ($a$ is prime here and $b \le a-1$)

I also suspect that the only composite values of $2n^2-1$ are those whose factors are from that set of a (like $7$, $17$, $23$ etc.).

I am trying to see if there anything else can be said about primality or compositness of those numbers $n$. Is there any other forms of n that can guarantee compositness (or primality)?

I would appreciate any ideas.

Thanks!

• One can get compositeness results, but primality results are another matter. Any polynomial of degree $\ge 1$, with positive lead coefficient, takes on infinitely many composite values. And there is no known quadratic polynomial that provably takes on infinitely many prime values, although it is reasonable to conjecture that any polynomial which is not always "obviously" composite for large enough $n$ is prime for infinitely many $n$. – André Nicolas May 27 '13 at 5:11
• Thanks Andre, interesting note – Anvar May 27 '13 at 5:31
• You are welcome. You may be interested in this article on the Bunyakovsky Conjecture. As a simple example, it is a long-standing (but still unproved) conjecture that there are infinitely many primes of the form $n^2+1$. There is strong numerical evidence for this, and even a conjectured formula for the approximate number of such primes $\le x$ that seems to fit computed data well. – André Nicolas May 27 '13 at 5:39

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$.

• Thanks Vadim, that make sense. – Anvar May 27 '13 at 5:26

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.

$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).

• That's interesting, thanks. – Anvar May 29 '13 at 6:42

I encountered this so I think that for

$n = (2m^2-1)k+m$ and $n = (2m^2-1)k+(2m^2-1-m)$

where $m\leq \sqrt\frac{n+1}{2}$

For such n forms .. $2n^2-1$ is composite.