## 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)$.

1. n^2+3n+2 factors as (n+1)(n+2)

For all odd values of n, (n+1) is even and so contains 2 as a factor. So we want either odd values of n that are 2 less than a multiple of 3, or one less than a multiple of 6. There are 663 multiples of 3 less than 1991, 332 of which are odd - each one has a corresponding n value. There are 331 multiples of 6 - each one also has a corresponding n value, so a total of 663 odd values of n that work.

For even numbers, there are 331 values of n that result in (n+2) containing a factor of 6, and 332 values that make (n+1) contain a factor of 3.

Total number of possible values for n is then 1326 ... I think

2. n^2 + 3n + 2 is always even, so we only want to concern ourselves with divisibility b 3. We have it for n \equiv 1, 2 \bmod 3, and for each case we have 663 possibilities, for a total of 1326.