IBM Ponder This #078 · October 2004

Puzzle for October 2004.

This month's puzzle is from IQSTAR.
Solutions to one or several parts are okay, but should be accompanied by a proof that your list contains all the possible values and only those, and should be original.

Part 1:
A polynomial is called "primitive" if all the coefficients are integers with their greatest common divisor (GCD) equal to 1. Let P(x) be a primitive polynomial of degree m in x. V(P) is the set of all P(n) where n takes all the integral values. G(P) is the GCD of the elements of V(P). For fixed m, what values can G(P) have?

Part 2:
Let P(x,y,z) be a primitive polynomial of total degree m in (x,y,z). (It involves monomials (x^i*y^j*z^k) where i,j,k are nonnegative integers with i+j+k bounded by m.) V(P) is the set of all P(n1,n2,n3) where n1,n2,n3 take on all the integral values. G(P) is the GCD of the elements of V(P). For fixed m, what values can G(P) have?

Part 3:

What if P(x,y,z) is of degree m separately in each variable? (For each nonzero coefficient, i,j,k are each bounded by m.)

Solution

Best opened after a real attempt

To be added.