Maths Olympiad Prep

Library / /6 of 7

Number theory Difficulty 5.2 AIME, harder Prove it Japan

xx, yy and zz are distinct 2-digit positive integers. The first digit of xx is equal to the second digit of yy, the first digit of yy is equal to the second digit of zz, and the first digit of zz is equal to the second digit of xx. How many positive integers can be the greatest common divisor of xx, yy and zz?

Solution

We can write x=10a+bx = 10a + b, y=10b+cy = 10b + c, z=10c+az = 10c + a with positive integers a,b,ca, b, c less than 1010. Let dd be the greatest common divisor of xx, yy and zz. 1111 cannot divide dd, since otherwise it contradicts the fact that xx, yy and zz are distinct.

x+y+z=(10a+b)+(10b+c)+(10c+a)=11(a+b+c)x + y + z = (10a + b) + (10b + c) + (10c + a) = 11(a + b + c) is divisible by dd. Since dd is not divisible by 1111, a+b+ca+b+c is divisible by dd. Thus da+b+c27d \le a+b+c \le 27.

Also, 100x10y+z=1000a+100b100b10c+10c+a=1001a100x - 10y + z = 1000a + 100b - 100b - 10c + 10c + a = 1001a is divisible by dd. Similarly, 1001b1001b and 1001c1001c are divisible by dd. So 1001k1001k and hence 91k91k is divisible by dd, where kk is the greatest common divisor of aa, bb and cc.

Since d27d \le 27 and k4k \le 4 (otherwise x=y=zx = y = z), dd is one of 1,2,3,4,7,13,14,211, 2, 3, 4, 7, 13, 14, 21 or 2626.

But, dd cannot be 2121, because a 2-digit multiple of 2121 must be 21,42,6321, 42, 63 or 8484, and we can't find xx, yy, zz among them with the required conditions. Similarly, dd cannot be 2626.

On the other hand, since (x,y,z)=(32,21,13),(64,42,26),(96,63,39),(88,84,48),(42,21,14),(65,52,26)(x, y, z) = (32, 21, 13), (64, 42, 26), (96, 63, 39), (88, 84, 48), (42, 21, 14), (65, 52, 26) and (84,42,28)(84, 42, 28) give examples for d=1,2,3,4,7,13d = 1, 2, 3, 4, 7, 13 and 1414, there are exactly 77 such dd's.

Want a route through all this instead of an archive? The track puts 2,000 problems in a working order, from AMC 10 level to the IMO shortlist.

Source: MathNet, licensed CC-BY-4.0. Statement and solution reproduced as published; topic and difficulty added by this site.