1988 AIME Problem 8

Attempt Problem 8 of the 1988 AIME below, then check your answer against the professionally curated solution from LIVE by Po-Shen Loh. You can also try the full timed exam, view all 1988 AIME solutions, or check the answer key.

All problems are used with official legal permission of the Mathematical Association of America (MAA).

8.

The function f,f, defined on the set of ordered pairs of positive integers, satisfies the following properties:

f(x,x)=x,f(x,y)=f(y,x),(x+y)f(x,y)=yf(x,x+y).\begin{gathered}f(x,x)=x,\\f(x,y)=f(y,x),\\(x+y)f(x,y)=yf(x,x+y).\end{gathered}

Calculate f(14,52).f(14,52).

Answer: 364
Concepts:functional equationgreatest common divisorleast common multiple
Difficulty rating: 2270
Small Hint:

Apply the third property to (x,yx)(x,y-x) when y>xy\gt x

Big Hint:

Compare the resulting subtraction rule with the same rule for lcm(x,y)\operatorname{lcm}(x,y)

Solution:

For y>x,y\gt x, the third property applied to (x,yx)(x,y-x) gives f(x,y)=yyxf(x,yx).f(x,y)=\frac{y}{y-x}f(x,y-x). The least common multiple obeys the identical relation, because gcd(x,y)=gcd(x,yx).\gcd(x,y)=\gcd(x,y-x). Hence the quotient f(x,y)lcm(x,y)\frac{f(x,y)}{\operatorname{lcm}(x,y)} is unchanged by each subtraction step of the Euclidean algorithm. On the diagonal it equals f(g,g)g=1,\frac{f(g,g)}{g}=1, so f(x,y)=lcm(x,y).f(x,y)=\operatorname{lcm}(x,y). Therefore f(14,52)=1452gcd(14,52)=364.\begin{aligned}f(14,52)&=\frac{14\cdot52}{\gcd(14,52)}\\&=364.\end{aligned}

← Problem 7#7
Full Exam

Problem 8 in Other Years