Putnam 1994

a, b, c, d are integers in the range 0 - 99. Show that if 101a -100·2^a + 101b - 100·2^b = 101c - 100·2^c + 101d - 100·2^d (mod 10100) then {a, b} = {c, d}.

Solution

We have immediately that a + b = c + d (mod 100) and 2^a + 2^b = 2^c + 2^d (mod 101). But by Fermat's little theorem 2¹⁰⁰ = 1 (mod 101), so 2^a+b = 2^c+d (mod 101).

Now (2^c - 2^a)(2^c - 2^b) = 2^2c - (2^a + 2^b)2^c + 2^a+b = 2^2c - (2^c + 2^d)2^c + 2^c+d = 0 (mod 101). But 101 is prime, so either 2^c = 2^a (mod 101), or 2^c = 2^b (mod 101). If 2^c = 2^a, then 2^d = 2^b, and so {2^a, 2^b} = {2^c, 2^d} (mod 101). Similarly if 2^c = 2^b (mod 101).

It remains to show that 2 is a primitive root of 101. 2¹⁰ = 1024 = 14 (mod 101), so 2²⁰ = 196 = -6 (mod 101), and 2⁵⁰ = 36·14 = 504 = -1 (mod 101). Hence 2 is a primitive root and so 2^m = 2ⁿ (mod 101) implies m = n (mod 100). We are told that a, b, c, d all lie in the range 0 to 99, so {2^a, 2^b} = {2^c, 2^d} (mod 101} implies {a, b} = {c, d}.

The solutions given on this site are not always complete, they are designed to be sufficient for anyone who has thought hard about the problem.

Putnam 1994

© John Scholes
jscholes@kalva.demon.co.uk
12 Dec 1998