IMO 2003 SL N8

Origin: IRN | Category: Number Theory

Problem

Let p be a prime number and let A be a set of positive integers that satisfies the following conditions: (i) the set of prime divisors of the elements in A consists of p−1 elements; (ii) for any nonempty subset of A, the product of its elements is not a perfect pth power. What is the largest possible number of elements in A?

Solution

Let p1, p2, . . . , pr be distinct primes, where r = p −1. Consider the sets Bi = {pi, pp+1 i , . . . , p(r−1)p+1 i } and B = %r i=1 Bi. Then B has (p −1)2 elements and satisfies (i) and (ii). Now suppose that |A| \geqr2 + 1 and that A satisfies (i) and (ii), and let {t1, . . . , tr2+1} be distinct elements of A, where tj = p \alphaj1 \cdot p \alphaj2 \cdot \cdot \cdot p\alphajr r . We shall show that the product of some elements of A is a perfect pth power, i.e., that there exist \tauj \in{0, 1} (1 \leqj \leqr2 + 1), not all equal to 0, such that T = t\tau1 1 \cdot t\tau2 2 \cdot \cdot \cdot t \taur2+1 r2+1 is a pth power. This is equivalent to the condition that r2+1  j=1 \alphaij\tauj \equiv0 (mod p) holds for all i = 1, . . . , r. By Fermat’s theorem it is sufficient to find integers x1, . . . , xr2+1, not all zero, such that the relation r2+1  j=1 \alphaijxr j \equiv0 (mod p) is satisfied for all i \in{1, . . . , r}. Set Fi = r2+1 j=1 \alphaijxr j. We want to find x1, . . . , xr such that F1 \equivF2 \equiv\cdot \cdot \cdot \equivFr \equiv0 (mod p), which is by Fermat’s theorem equivalent to

F(x1, . . . , xr) = F r 1 + F r 2 + \cdot \cdot \cdot + F r r \equiv0 (mod p). (1) Of course, one solution of (1) is (0, . . . , 0): we are not satisfied with it because it generates the empty subset of A, but it tells us that (1) has at least one solution. We shall prove that the number of solutions of (1) is divisible by p, which will imply the existence of a nontrivial solution and thus complete the proof. To do this, consider the sum  F(x1, . . . , xr2+1)r taken over all vectors (x1, . . . , xr2+1) in the vector space Zr2+1 p . Our statement is equiv- alent to  F(x1, . . . , xr2+1)r \equiv0 (mod p). (2) Since the degree of F r is r2, in each monomial in F r at least one of the variables is missing. Consider any of these monomials, say bxa1 i1 xa2 i2 \cdot \cdot \cdot xak ik . Then the sum  bxa1 i1 xa2 i2 \cdot \cdot \cdot xak ik , taken over the set of all vectors (x1, . . . , xr2+1) \inZr2+1 p , is equal to pr2+1−u \cdot  (xi1,...,xik)\inZkp bxa1 i1 xa2 i2 \cdot \cdot \cdot xak ik , which is divisible by p, so that (2) is proved. Thus the answer is (p −1)2.