Robert Gerbicz wrote: The answer is k=9. k=8 isn't good, because let B={2,4,6,8,10,12,14,16} the all even numbers, and $ {a}^{2}+{b}^{2}$ is divisible by 4 so can't be prime. k=9 is good, because consider the following partitions of A: $ (15,2)$ $ (11,4)$ $ (5,6)$ $ (13,8)$ $ (3,10)$ $ (7,12)$ $ (9,14)$ $ (1,16)$ In each pair $ {a}^{2}+{b}^{2}$ is a prime number. If we select $ 9$ numbers from $ A$ then we should select a pair from these $ 8$ pairs, proving the statement.