1

Please see the below proof from the Book of Proof by Richard Hammack. I've broken out the step I have a question on and made the text preceding the equation bold.

Suppose $f(x) = a_0 + a_1x + a_2x^2 + \cdots + a_nx^n$ is a polynomial of degree $1$ or greater, and for which each coefficient $a_i$ is in $\mathbb {N}$. Then there is an $n\in\mathbb {N}$ for which the integer $f(n)$ is not prime.

$Proof$. Note that, because the coefficients are all positive and the degree is greater than $1$, we have $f(1)>1$. Let $b=f(1)>1$. Now, the polynomial $f(x)-b$ has a root $1$, so $f(x)-b=(x-1)g(x)$ for some polynomial $g$. Then $f(x)=(x-1)g(x)+b$.

Now note that $f(b+1)=bg(b)+b=b(g(b)+1)$.

If we can now show that $g(b)+1$ is an integer, then we have a nontrivial factoring $f(b+1)=b(g(b)+1)$, and $f(b+1)$ is not prime. To complete the proof, use the fact that $f(x)-b=(x-1)g(x)$ has integer coefficients, and deduce that $g(x)$ must also have integer coefficients. $\Box$

My question is how is it that the output from the function is simplified to

$$f(b+1)=bg(b)+b=b(g(b)+1).$$

Shouldn't $f(b+1)$ give

$$f(b+1)=bg(b+1)+b=b(g(b+1)+1) \text{ ?}$$

ClownInTheMoon
  • 1,987

1 Answers1

1

Yes: $f(b+1)$ is what you get when substitute $x$ with $b+1$, so $$ f(b+1)=(b+1-1)g(b+1)+b=b(g(b+1)+1) $$ The rest of the proof goes along the same way, because $g(x)$ is indeed a polynomial with integer coefficients.

However, one should also prove that $g(b+1)\ne0$ and $g(b+1)\ne-2$ (note that $f(b+1)\ne0$, so the case $g(b+1)=-1$ is not possible).

egreg
  • 238,574