Do there exist 100 positive integers not exceeding 25000 such that the sum of every pair is distinct?
Solution
Answer: yes.
We show how to find p integers <= 2p2 for any prime p. Since 2.1012 < 25000, that is sufficient.
Let n denote the residue of n2 mod p. We claim that the integers 2p + 1, 4p + 2, 6p + 3, ... , 2p p + p work. If (2ap + a) + (2bp + b) = (2cp + c) + (2dp + d), then 2(a + b)p + (a + b) = 2(c + d)p + (c + d) and hence a + b = c + d and a + b = c + d (since n < p). Hence a + b = c + d mod p and a2 + b2 = c2 + d2 mod p. So a = c + d - b mod p. Substituting in the next equation, (c + d - b)2 + b2 = c2 + d2 mod p, so 2(b2 - bc - bd - cd) = 0 mod p, or 2(b - c)(b - d) = 0 mod p. Hence b = c or d. So the sum of every pair is distinct.
© John Scholes
jscholes@kalva.demon.co.uk
14 Oct 2002