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.

A "never prime" expression must be composite for every prime $p$, so it should carry a divisibility argument, and the natural modulus is $3$.

If $p \ne 3$, then $p$ is not divisible by $3$, so $p^2 \equiv 1 \pmod 3$. Then
$$p^2 + 26 \equiv 1 + 26 = 27 \equiv 0 \pmod 3,$$
and $p^2 + 26 > 3$, so it is composite. If $p = 3$, then $p^2 + 26 = 35 = 5 \cdot 7$, also composite. Hence (C) is never prime.

The other constants ($16, 24, 46, 96$) are not $2 \bmod 3$, so this argument fails for them, and indeed each produces a prime: $5^2 + 16 = 41$, $7^2 + 24 = 73$, $5^2 + 46 = 71$, $19^2 + 96 = 457$.

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