A chooses a positive integer X ≤ 100. B has to find it. B is allowed to ask 7 questions of the form "What is the greatest common divisor of X + m and n?" for positive integers m, n < 100. Show that he can find X.
Solution
The idea is that X can be regarded as having 7 binary digits b6b5...b0 and we can find each digit with one question. If there was no restriction on the numbers m, n, then the procedure would be trivial: having determined the last k binary digits which give a number m, we then ask for gcd(X - m, 2k+1). If it is 2k+1, then bk = 0, if it is 2k, then bk = 1. Given the restrictions, we have to use a slight variant on this procedure.
For b0 we can ask for gcd(X+1,2). If it is 1, then b0 = 0. If it is 2, then b0 = 1. Now if we have found b0, b1, ... bk-1 with k ≤ 5, we want to subtract off b = bk-1...b1b0. So we add m = 2k+1 - b. Then the last k+1 digits of X + 2k+1 - b are bk0...0, so gcd(X+m,2k+1) is 2k+1 if bk = 0, or 2k if bk = 1. That gives us b0, b1, ... , b5 in the first 6 questions. If b = b5b4...b0, we know that X = b or b+64. These are different mod 3. So we take m = 1, 2 or 3 to give b + m a multiple of 3 and and take n = 3. Then gcd(X+m,n) distinguishes b and b+64.
© John Scholes
jscholes@kalva.demon.co.uk
20 December 2003