Find the Good Number

We organize the numbers into 10 pairs as follows: $\begin{aligned} 1^2 + 20^2 &= 401 \\ 2^2 + 3^2 &= 13 \\ 4^2 + 15^2 &= 241 \\ 5^2 + 16^2 &= 281 \\ 6^2 + 19^2 &= 397 \\ 7^2 + 8^2 &= 113 \\ 9^2 + 10^2 &= 181 \\ 11^2 + 14^2 &= 317 \\ 12^2 + 13^2 &= 313 \\ 17^2 + 18^2 &= 613 \end{aligned}$ Notice that all of these sums are prime. Therefore, 11 is a good number--if we pick any subset of $M$ of size 11, it will contain one of these pairs $(a,b)$ , and $a + b$ will be prime. However, any number $n \le 10$ is not good, because we can just take the subset of size $n$ to be the first $n$ even numbers. So $\boxed{11}$ is the smallest good number.

Let $K=\left \{ 1^2,3^2,5^2,\dots , 17^2,19^2 \right \}$ . Since the sum of any two elements of $K$ is not prime, $n \ge 11$ .

Now let's show that $n \le 11$ . We partition $M$ into $10$ subsets of order $2$ such that the sum of two elements in any subset is prime:

$M=\left \{1^2,4^2 \right \} \cup \left \{2^2,3^2 \right \} \cup \left \{5^2,8^2 \right \} \cup \left \{6^2,11^2 \right \} \cup \left \{7^2,10^2 \right \} \cup \left \{9^2,16^2 \right \} \cup \left \{12^2,13^2 \right \} \cup \left \{14^2,15^2 \right \} \cup \left \{17^2,18^2 \right \} \cup \left \{19^2,20^2 \right\}$ .

Any subset of $M$ having $11$ elements contains both elements of at least one of these $10$ subsets.

The answer: $n=\boxed{11}$