<s>[INST] 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!
 [/INST] 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$.
</s>