Putnam 02/B6 solution

63rd Putnam 2002

Problem B6

Let p be prime and q = p². Let D be the determinant:


   x     y     z

   x^p    y^p    z^p

   x^q    y^q    z^q

Show that we can find a set of linear polynomials ax + by + cz (with a, b, c integers) whose product Q equals D mod p. (In other words, after expansion the corresponding coefficients of Q and D are equal mod p.)

Solution

Since p is prime, we have (X^p + Y^p + Z^p) = (X + Y + Z)^p mod p. Also (X + Y + Z)^q = (X^p + Y^p + Z^p)^p = X^q + Y^q + Z^q mod p. Put X = ax, Y = bY, Z = cZ, for a, b, c integers. Then since a^p = a mod p, b^p = b mod p, c^p = c mod p, we have a x^p + b y^p + c z^p = (ax + by + cz)^p and a x^q + b y^q + c z^q = (ax + by + cz)^q.

So if we take as the new first column of the determinant a x first col + b x second col + c x third col, then mod p the new first column is k, k^p, k^q, where k = ax + by + cz. So the determinant has a factor ax + by + cz. This is true for all a, b, c. Now consider the following p²+p+1 factors mod p:


x

y, y + x, y + 2x, y + 3x, ... , y + (p-1)x

z, z + x, z + 2x, z + 3x, ... , z + (p-1)x

z+y, z+y+x, z+y+2x, ... , z+y+(p-1)x

z+2y, z+2y+x, z+2y+2x, ... , z+2y+(p-1)x

...

z+(p-1)y, z+(p-1)y+x, z+(p-1)y+2x, ... , z+(p-1)y+(p-1)x

Evidently none is of these is a multiple of another, so their product Q must divide D. But D has total degree 1+p+q, which is the same as the total degree of Q. So D must be a multiple of Q. But the only term x y^pz^q in the expansion of Q comes from taking the first term of each factor, so the coefficient of x y^pz^q in Q is 1. That is also the coefficient in the expansion of D, so D = Q.

63rd Putnam 2002