Solution: Day 3, problem 1
The polynomial in question has the form f(x) = a0xn + ... + an where each ai is between
0 and 9, the leading coefficient a0 is positive, and f(10) is prime. Suppose that f factors
non - trivially as g(x)h(x), where by Gauss's lemma we can suppose that g(x), h(x) are in Z[x].
The primality
of f(10) implies that one of g(10) and h(10), say the former, equals 1 (or - 1, but then replace
g by - g). Write g(x) = c (x - b1)(x - b2) ... (x - bd), where d = deg(g) >= 1 and c is an integer.
We claim that each root
b = bj is in the union of the (closed) left half - plane and the disk of radius 4 centred at the origin. Indeed,
b is also a root of f(x), so if Re(b) > 0 and |b| >= 4 then we would obtain a contradiction from
1 <= a0 <= Re(a0 + a1b-1) = Re( -a2b-2 - ... - anb-n) <= 9|b|-2/(1 - b-1) <= 3/4. It follows
that |10 - b| >= 6, so 1 = |g(10)| = |c (10 - b1) ... (10 - bd)| >= 6d, which is a contradiction.
Return to the problems.
Don Zagier 1996