## Saturday, June 17, 2006

### Egyptian. Topic: Number Theory. Level: AIME.

Problem: (1991 India National Olympiad - #10) For any positive integer $n$, let $s(n)$ denote the number of ordered pairs $(x,y)$ of positive integers for which $\frac{1}{x} + \frac{1}{y} = \frac{1}{n}$. Determine the set of positive integers for which $s(n) = 5$.

Solution: Rewrite the equation as

$n(x+y) = xy$

$(x-n)(y-n) = n^2$.

So for each pair $(a,b)$ with $ab = n^2$, there exist a pair $(x,y) = (a+n, b+n)$ satisfying

$\frac{1}{x}+\frac{1}{y} = \frac{1}{n}$.

Hence we want to find an $n^2$ with $5$ distinct factors. We see that $n^2 = p^4$ for $p$ prime is the only case (since $5$ itself is prime, meaning $n = p^rq^s$ is not possible), so we thus have $s(n) = 5$ for $n = p^2$, where $p$ is any prime. QED.

--------------------

Comment: A standard problem involving Simon's Favorite Factoring Trick and counting the number of divisors. SFFT is always something to look for when you have $xy, x, y$ terms (sorta like completing the square except not).

--------------------

Practice Problem: (1991 India National Olympiad - #1) Find the number of positive integers $n$ for which

(i) $n \leq 1991$;

(ii) $6$ is a factor of $(n^2 + 3n +2)$.