Minimal Counterexample for False Prime-Generating Quadratic Polynomials (Chartrand Ex 7.66)

Question

Factor the quadratic: $n^2 \pm n + 41 = n(n \pm 1) + 41 = n\left[(n \pm 1) + \cfrac{41}{n}\right]$.
So if we find at least one $n$ such that $\frac{41}{n}$ is an integer, or equivalently an $n$ such that $n \mid 41$,
then we'll have proven by counterexample that these 2 quadratics generate primes only for all $0 \leq n \leq \text{some natural number}$. By inspection, $n = 41$ works as one such value.

I see that $n = 41$ is one counterexample for $n^2 - n + 41$. Still, for $n^2 + n + 41$, the minimal counterexample is $n = 40$ because $\quad 40^2 + 40 + 41 \; = \; 1681 = \; 41^2$ = composite number.

$\Large{\text{1.}}$ What divulges/uncloaks $n = 40$ as the minimal counterexample for $n^2 - n + 41$?

$\Large{\text{2.}}$ How and why would one divine/previse to factor (as above) $n^2 \pm n + 41 = n(n \pm 1) + 41 $?

$\Large{\text{3.}}$ How and why would one divine/previse the failure of $n^2 \pm n + 41$ for some $n$?

Supplementary dated Jan 7 2014:

$\Large{\text{2.1.}}$ I still don't register the factoring. Customarily, I'd factor out $a_0$ as so: $\color{green}{f(a_0)=a_0\left[a_m (a_0)^{m-1} + \ldots + a_1 + 1\right]}.$
Yet $Q2$ compels: $\color{brown}{f(a_0)=a_0\left[a_m (a_0)^{m-1} + \ldots + a_1\right] + a_0}.$?

$\Large{\text{3.1.}}$ If the green is composite, then the green contradicts the proposition that a polynomial generates primes. For the green to be composite, $\color{green}{a_0} \neq \pm 1$.
Still, wouldn't you also need $\color{green}{\left[a_m (a_0)^{m-1} + \ldots + a_1 + 1\right]} \neq \pm 1$ ?

Answer 1

1. Nothing written so far actually proves $n=40$ is the minimal counterexample for $n^2+n+41.$ All that has been shown is that the factorization $n(n+1)+41$ makes it clear that $n=40$ is a counterexample, while the second factorization you wrote makes it clear that $n=41$ is also a counterexample.

2. For a similar reason to what I write below for 3.

3. For any polynomial $f(n)=a_m n^m + \ldots a_1 n + a_0,$ putting $n=a_0$ shows that $a_0$ divides $f(a_0),$ so if we have such a polynomial where $a_0 \neq \pm 1$ then we automatically know we have a counterexample at $n=|a_0|.$

Answer 2

To expand on Ragib Zaman's answer to Point 3: if $f(n)=a_mn^m+\ldots a_1n+a_0,$ than $f(ka_0)$ is divisible by $a_0$ for every $k\in\mathbf{Z}.$ Write $$ f(ka_0)=a_0(a_ma_0^{m-1}k^m+a_{m-1}a_0^{m-2}k^{m-1}+\ldots+a_1k+1). $$ If $a_0$ is composite, then $f(ka_0)$ is composite for every $k.$ If $a_0$ is prime, then $f(ka_0)$ is composite as long as the factor in parentheses is not $\pm1.$ But there are at most $2m$ values of $k$ that solve $$ a_ma_0^{m-1}k^m+a_{m-1}a_0^{m-2}k^{m-1}+\ldots+a_1k+1=\pm1. $$ (There are at most $m$ values of $k$ for each choice of sign on the right hand side.) Hence $f(ka_0)$ will be composite for infinitely many values of $k\in\mathbf{Z}.$