The question is in MIT Mathematics for CS assignments but unfortunately there is no solutions.
-> I do understand that it is false if we use $n = c$ or $n = c-1$ but cannot formally write it as expected in the problem like what would be the different if $c$ is prime or not ?
For $n = 40$, the value of polynomial $p(n) := n^2 + n + 41$ is not prime, as noted in Chapter 1 of the Course Text. But we could have predicted based on general principles that no nonconstant polynomial, $q(n)$, with integer coefficients can map each nonnegative integer into a prime number. Prove it. Hint: Let $c := q(0)$ be the constant term of $q$. Consider two cases: c is not prime, and $c$ is prime. In the second case, note that $q(cn)$ is a multiple of $c$ for all $n \in Z$. You may assume the familiar fact that the magnitude (absolute value) of any nonconstant polynomial, $q(n)$, grows unboundedly as $n$ grows.
If $q(0)$ is not prime, then you're done: you have a value at which the polynomial is not prime.
If $c = q(0)$ is prime, then since $q$ is not constant, we may write $$q(n) = c + np(n),$$ where $p(n)$ is a non-zero polynomial. Therefore, $$q(cn) = c + cnp(cn) = c(1 + np(cn)),$$ which confirms the hint: $q(cn)$ is divisible by $c$. Therefore, if $q(cn)$ is always prime, then it is always $c$, which is to say that, for all $n$, $$1 + np(cn) = 1 \iff np(cn) = 0.$$ But $np(cn)$ is a non-zero polynomial, with finitely many roots by the fundamental theorem of algebra. So $np(cn) = 0$ for only finitely many $n$ (or maybe none at all), which is a contradiction.