Putnam 1994

------
 
 
Problem B6

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

 

Solution

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

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

It remains to show that 2 is a primitive root of 101. 210 = 1024 = 14 (mod 101), so 220 = 196 = -6 (mod 101), and 250 = 36·14 = 504 = -1 (mod 101). Hence 2 is a primitive root and so 2m = 2n (mod 101) implies m = n (mod 100). We are told that a, b, c, d all lie in the range 0 to 99, so {2a, 2b} = {2c, 2d} (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