Let $f(x) = x^m + a_1x^{m−1} + · · · + a_{m−1}x + a_m$, with $a_j \in \mathbb{Z}$, be a polynomial with integer coefficients and $m \geq 1$.
(i) Show that if $a$ and $b$ are integers with $a \equiv b \pmod{n}$, then $f(a) \equiv f(b) \pmod{n}$. I think I am supposed to use the polynomial division algorithm here?
(ii) Suppose that for some integer $a$, $f(a) = p$ is a prime. Show that, if $f(b) = q$ is also a prime for some integer $b$ with $b \equiv a \pmod{p}$, then $p = q$.
(iii) As in part (ii), suppose that for some integer $a$, $f(a) = p$ is a prime. Show that there must be an integer $b$ with $f(b)$ not a prime. (Hence there are no ‘magic’ polynomials, giving only prime values. ) Hint: consider the polynomial $f(x) − p$ and use (ii).
Please advise on question above.
Thank you!
i) If you can prove $a\equiv b$ and $j \equiv k$ that $aj \equiv bk$ and $a+j \equiv b+k$ you are done.
By induction you can prove that if $a_i \equiv b_i$, and $a_1 + .... + a_m \equiv b_1 + .... + b_m$ then $(a_1+ ......+a_m) + a_{m+1} \equiv (b_1 + .... + b_m) + b_{m+1}$ so the result holds for all sums no matter how many sumands.
Similarly for products no matter how many multicands.
And if true for products then true for powers which are just products where all multicands are equal.
And if true for products then true for polynomials which are a sum of products of coefficients and powers.
ii) apply i)
If $a \equiv b \pmod p$ then $0\equiv p = f(a)\equiv f(b) =q\pmod p$. So $q \equiv 0 \pmod p$ so $p|q$. But $q$ is prime. So $p=q$.
iii) Not sure I'm getting their hint.
Suppose $f(n)$ is prime for all integers $n$.
But one of the following must be true:
1) $f(n)$ is never prime for any integer $n$.
If so we have nothing to prove.
2) The is exactly one prime $p$ that $f(n)$ is ever equal to.
As $n\to \infty$ we have $f(n)\to \infty$ so $f$ has more than value. So some values are not $p$ and as $p$ was the only prime some values are not prime.
3) There is an $a$ and $b$ so that $f(a)=p$ a prime and $f(b)=q$ a prime not equal to $p$ then by Bizout's Theory there are $Mp + Nq = a-b$ so $b +Nq = a-Mp$. Let $k=b+Nq=a-Mp$
So by ii) if $f(k)$ is prime then $f(b+Nq) =q$ but if $f(k)$ is prime then $f(a-Mp)=p$ so that's a contradiction.
So $f(k)$ is not prime.
So there will always be a value, $k$ where $f(k)$ is not prime.