Arithmetic Prime!

Note that $k\neq1$ since $3(1)+1=4$ is not prime and $k\neq 2$ since $4(2)+1=9$ is not prime. Now, $k\not\equiv 1\bmod 2$ , since, if it were, $k+1 \equiv 0\bmod 2$ and, since we already know $k\neq 1$ , this cannot be prime.

Next, we consider $k \bmod 3$ : $k\equiv 1\bmod 3$ and $k\equiv 2\bmod 3$ are both impossible, since they lead to $2k+1\equiv 0\bmod 3$ and $k+1\equiv0\bmod3$ , respectively (remember $k\neq 2$ . Thus $k\equiv 0\bmod 3$ .

Similarly, we can show that $k\not\equiv 1,2,3,4\bmod 5$ , and so $k\equiv 0\mod 5$ . For $k\bmod7$ , we find that $k\equiv 0,1,4\bmod7$ are all possibilities.

We could continue to test $k\bmod 11$ , but at this point it is more efficient to try numbers based on the information we have. We need only test numbers that are multiples of 2, 3 and 5 (that is, multiples of 30) and which are congruent to 0, 1 or 4 mod 7. Thus our candidates are: $\begin{array}{rl} 60 & 4(60) + 1 = 121 = 11^2 \text{ is not prime}\\ 120 & 1(120) + 1 = 121 = 11^2 \text{ is not prime}\\ 210 & 4(210) + 1 = 841 = 29^2 \text{ is not prime}\\ 270 & 4(270) + 1 = 1081 = 23\times47 \text{ is not prime}\\ \boxed{330} & \text{All four are prime!} \end{array}$