2018 AMC 10B Problem 11

To show an expression is never prime, we need a reason that works for every prime at once. To rule out the other choices, one prime example each is enough. Start by plugging in small primes.

1. Try a few primes.

$41$ is prime, so (A) is out. $73$ is prime, so (B) is out. $71$ is prime, so (D) is out.
2. Notice a pattern in (C). The (C) column gives $51 = 3 \times 17$ and $75 = 3 \times 25$, both multiples of $3$. Let us see why.
3. Squares and the number 3. A prime other than $3$ is not a multiple of $3$, so it is one more or one less than a multiple of $3$. Squaring such a number always gives one more than a multiple of $3$. For example $5^2 = 25 = 24 + 1$ and $7^2 = 49 = 48 + 1$.
4. Add 26. One more than a multiple of $3$, plus $26$, is $27$ more than a multiple of $3$, which is itself a multiple of $3$. And $p^2 + 26$ is bigger than $3$, so it is not prime.
5. The one prime left, $p = 3$. Then $p^2 + 26 = 35 = 5 \times 7$, not prime either.

So $p^2 + 26$ is never prime. (For completeness, (E) can be prime: $19^2 + 96 = 457$, which is prime.)

The answer is $\boxed{\textbf{(C)}\ p^2+26}$.

"Never prime" means "always has a small factor." Looking at remainders when dividing by $3$ is the natural test, because every prime except $3$ has a square that is one more than a multiple of $3$. So the added number must be two more than a multiple of $3$, and $26$ is the only choice like that.

Use the remainder idea first. In the language of congruences, $p^2 \equiv 1 \pmod 3$ for every prime $p \ne 3$, which just means $p^2$ leaves remainder $1$ when divided by $3$. For $p^2 + c$ to be a multiple of $3$ we need $c$ to leave remainder $2$. The constants $16, 24, 26, 46, 96$ leave remainders $1, 0, 2, 1, 0$, so only $26$ can work. Then check $p = 3$ separately: $35$ is not prime.