IMO shortlist 1985/1 solution

26th IMO 1985 shortlist

Problem 1

Show that if n is a positive integer and a and b are integers, then n! divides a(a + b)(a + 2b) ... (a + (n-1)b) b^n-1.

Solution

Solution by Demetres Christofides

If p^k is the highest power of a prime p dividing n!, then k = [n/p] + [n/p²] + [n/p³] + ... . We have p ≥ 2, so [n/p] + [n/p²] + [n/p³] + ... ≤ [n/2] + [n/4] + [n/8] + ... < n/2 + n/4 + n/8 + ... = n. Note that the inequality is strict, because [n/2] + [n/4] + [n/8] + ... has only finitely many non-zero terms. But k is integral, so k ≤ n-1.

If p divides b, then p^n-1 divides b^n-1 and hence p^k divides b^n-1. So suppose p does not divide b.

The set S = {a, a+b, a+2b + ... + a+(n-1)b} contains [n/p^r] complete sets of residues mod p^r, so it contains at least [n/p^r] numbers divisible by p^r. Suppose it has exactly a_r numbers divisible by p^r. Then it has a_r - a_r+1 numbers divisible by p^r but not p^r+1, so the product of its elements is divisible by (a₁ - a₂) + 2(a₂ - a₃) + 3(a₃ - a₄) + ... = a₁ + a₂ + a₃ + ... powers of p. But a₁ + a₂ + a₃ + ... ≥ [n/p] + [n/p²] + [n/p³] + ... = k. So p^k divides a(a+b)(a+2b) ... (a+(n-1)b).

26th IMO shortlist 1985