1995 AIME Problem 8

Attempt Problem 8 of the 1995 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 1995 AIME solutions, or check the answer key.

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

8.

For how many ordered pairs of positive integers

(x,y),

with

y<x\leq100,

are both

\frac{x}{y}

and

\frac{x+1}{y+1}

integers?

Answer

Answer: 85

Concepts:divisibility floor and ceiling functions counting pairs

Difficulty rating: 2060

Small hint:

Write

x=ay

and reduce

x+1

modulo

y+1

Big hint:

The quotient

a

must have the form

1+t(y+1)

; count the possible positive values of

t

Solution:

Write

x=ay.

Modulo

y+1,

we have

y\equiv-1,

so

x+1

is divisible by

y+1

exactly when

a\equiv1\pmod {y+1}.

Since

x>y,

write

a=1+t(y+1)

with

t\geq1.

The bound

x\leq100

becomes

t\leq\left\lfloor\frac{100-y}{y(y+1)}\right\rfloor.

Only

1\leq y\leq9

contribute, giving

\begin{aligned}49+16+8&+4+3\\&+2+1+1+1\\&=85.\end{aligned}