p is an odd prime. The integers a, b, c, d are not multiples of p and for any integer n not a multiple of p, we have {na/p} + {nb/p} + {nc/p} + {nd/p} = 2, where { } denotes the fractional part. Show that we can find two of a, b, c, d whose sum is divisible by p.
Solution
Solution by Michael J Doré
n denote the residue of n mod p, so n = 0, 1, 2, ... , or p-1. Thus {na/p} = na/p, and we have that na + nb + nc + nd = 2p for n not a multiple of p.
Let ω be a complex pth root of 1. We show first that ω + 2ω2 + 3ω3 + ... + (p-1)ωp-1 = p/(ω - 1). Suppose the sum is S. Then (1 - 2ω + ω2)S = ω - pωp + (p-1)ωp+1 (we need only look at the two lowest and two highest powers - the others all cancel because k - 2(k-1) + (k-2) = 0) = p(ω - 1). Hence S = p/(ω - 1).
Take residues a', b', c', d', so that aa' = bb' = cc' = dd' = 1 mod p. Then for any integers m, n we have mnaa' = mn mod p. Hence -ma' na = -mn mod p. Hence ω-ma' na = ω-mn. So na ω-ma' na = na ω-mn. Similarly for b, c, d. Take n not a multiple of p and add the four equations to get: na ω-ma' na + nb ω-mb' nb + nc ω-mc' nc + nd ω-md' nd = 2p ω-mn.
As n runs through 1, 2, ... , p-1, each of na, nb, nc, nd runs through a complete set of non-zero residues. If we take m to be not a multiple of p, then so does -mn, so adding the equations for n = 1, 2, ... , p-1, we get na ∑ kω-a'mk + ∑ k ω-b'mk + ∑ kω-c'mk + ∑ kω-d'mk = 2p(ω + ω2 + ... + ωp-1) = -2p.
Since ω-a'm is also a complex pth root of 1, we have ∑ kω-a'mk = p/(ω-a'm - 1) and similarly for the other terms. So the equation becomes: 1/(ω-a'm - 1) + 1/(ω-b'm - 1) + 1/(ω-c'm - 1) + 1/(ω-d'm - 1) = -2.
Multiplying through by (ω-a'm - 1)(ω-b'm - 1)(ω-c'm - 1)(ω-d'm - 1), expanding and simplifying, we get 2 + ω-a'm-b'm-c'm + ω-a'm-b'm-d'm + ω-a'm-c'm-d'm + ω-b'm-c'm-d'm = ω-a'm + ω-b'm + ω-c'm + ω-d'm + 2ω-a'm-b'm-c'm-d'm (*). Note that this equation is also true for m = 0 (when it is just 5 = 5). Now sum the equations for m = 0, 1, 2, ... , p-1. We have ∑ ωk = p if k is a multiple of p, and 0 otherwise. Obviously the first term ∑ 2 gives 2p and the other terms on the lhs give non-negative sums, so ∑ lhs is at least 2p. The first four terms on the rhs all have zero sum, so the last term must have sum 2p, so a' + b' + c' + d' must be a multiple of p. Thus (*) becomes ωa'm + ωb'm + ωc'm + ωd'm = ω-a'm + ω-b'm + ω-c'm + ω-d'm. Multiply through by ω-a'm and sum for m = 0, 1, 2, ... , p-1. The first term on the lhs has sum p and the others have non-negative sum. The first term on the rhs has zero sum, so one of the others must have positive sum. Hence p divides at least one of (a'+b'), (a'+c'), (a'+d'). Without loss of generality it divides a' + b'. In other words a' + b' = 0 mod p. Multiplying by ab, we get a + b = 0 mod p.
© John Scholes
jscholes@kalva.demon.co.uk
2 Jan 2003
Last corrected/updated 2 Jan 2003