1

Show that if $f(x)=a_nx^n+\cdots a_1x+a_0$ with $a_i \in \mathbb{Z}$, then there is a positive integer $y$ such that $f(y)$ is composite.

To prove this, we suppose that $f(x)=p$. Then for $f(x+kp)$ we have $f(x)+Kp$ where $K$ is a constant. I'm stuck on a specific part of understanding this proof, why is it that since $p \mid f(x) \Rightarrow p \mid (f(x)+kP)$. I'm also stuck understanding why $f(x+kp)$ is necessarily also prime.

emka
  • 6,494
  • Would you mind writing the proof completely? From what I understand, you're assuming $f(z)$ is prime for all $z\in\Bbb Z$ (since this is a proof by contradiction). As for your questions: 1) If $p\mid a$ and $p\mid b$, then $p\mid a+b$. 2) $f(x+kp)=p$ because $p\mid f(x+kp)$ and $f(x+kp)$ is prime. –  Jan 17 '14 at 05:36
  • Here is the complete proof that I am trying to parse: http://imgur.com/ztW4LGO – emka Jan 17 '14 at 05:44
  • I guess my comment pretty much answers your questions then. –  Jan 17 '14 at 05:47
  • Why is true that $f(x+kp)$ is prime? I never made an assumption that it is prime. – emka Jan 17 '14 at 16:45
  • Yes, you did. You're attempting a proof by contradiction, which means you assume $f(z)$ is prime for all $z\in\Bbb Z$. –  Jan 18 '14 at 01:50
  • 1
    I don't see the hypothesis $n>0$, but I think it is necessary. – Marc van Leeuwen Jun 28 '14 at 04:51
  • 1
    Also your title is confusing: you should put "for a(ny) polynomial with..." before "there is a positive integer", or else it means something different from what you want (and patently false). – Marc van Leeuwen Jun 28 '14 at 04:54

1 Answers1

0

Look at $(x+kp)^n$

$$ (x+kp)^n = x^n + {n \choose 1} x^{n-1} k p + {n \choose 2} x^{n-2} k^2 p^2 + \cdots \\ = x^n + \alpha_n p \text{ where $\alpha_n$ is an integer} $$ Similarly for other powers. This gives

$$ f(x+kp) = a_n (x^n + \alpha_n p) + a_{n-1} (x^{n-1} + \alpha_{n-1} p) \cdot \\= a_n x^n + a_{n-1} x^{n-1} + \cdots + (a_n \alpha_n + a_{n-1} \alpha_{n-1}+\cdots) p\\ =f(x) + K p $$

user44197
  • 9,730