1998 IMO Problems/Problem 3

Problem

For any positive integer $n$ , let $d(n)$ denote the number of positive divisors of $n$ (including 1 and $n$ itself). Determine all positive integers $k$ such that $d(n^2)/d(n) = k$ for some $n$ .

Solution

First we must $d$ etermine gener $a$ l values for $d(n)$ : Let $n=p1 ^ a1 * p2 ^ a2 * .. * pc ^ ac$ , if $d$ is an ar $b$ itr $a$ ry divisor of $n$ then $d$ must have the same prime factors of $n$ , each with an exponent $b_i$ being: $0\leq b_i\leq a_i$ . Hence there are $Ai + 1$ choices for each exponent of Pi in the number d => there are $(a_1 + 1)(a_2 + 1)..(a_c + 1)$ such d

$\implies d(n) = (a_1 + 1)(a_2+1)..(a_c+1)$ where $a_i$ are exponents of the prime numbers in the prime factorisation of $n$ .

$\implies d(n^2)/d(n) = {(2a_1 + 1)(2a_2 + 1)..(2a_c + 1)}/{(a_1+1)..(a_c+1)}$

So we want to find all integers $k$ that can $b$ e represented by the product of fractions of the form $(2n+1)/(n+1)$ Obviously $k$ is odd as the numerator is always odd. It's possible for 1 (1/1) and 3 $(5/3 * 9/5)$ , which suggests that it may be possible for all odd integers, which we can show by induction.

$P(k)$ : It's possible to represent $k$ as the product of fractions $(2n+1)/(n+1)$

Base case: $k = 1: (2(0) + 1) / (0 + 1)$ Now assume that for $k\geq 3$ it's possible for all odds < $k$ .

Since $k$ is odd, $k+1 = 2^zy$ where $y$ is odd and $y$ < $k$

Let there be a number $x$ s.t $k-y=x\implies k+1 = 2^z(k-x)\implies (2^zx+1)/(2^z-1)=k$

Also consider $k/y$ . It is sufficient to show that $k/y$ can be represented by a product of fractions of the form $2n+1/n+1$ in order to show $k$ can be represented by product of fractions $2n+1/n+1$ , since $y$ can be represented in such a manner too.

$k/y = k/(k-x) = 1/(1 - x/k)$

Using our definition of $k$ in terms of $x$ :

$k/y = 1/({1 - {2^z-x}/{2^zx+1}}) = {2^zx+1}/{x+1}$

And that is simply the product of fractions: ${2x+1}/{x+1} * {4x+1}/{2x+1} * .. * {2^zx+1}/{2^{z-1}x}$ .

We have shown that $k/y$ can be written s.t it's a product of fractions of the form ${2n+1}/{n+1}\implies k$ can be written in such a way too.

Hence we have shown that all odds less than $k$ satisfies $P(n)\implies P(k)$ is true. Since we have shown P(1) is true, it must hence be true for all odd integers.

Therefore, $d(n^2)/d(n) = k\iff k$ is odd, for some n. I.E all odd $k$ satisfy the condition posed in the question.∎

-dabab_kebab (wrote this solution)

1998 IMO (Problems) • Resources
Preceded by Problem 2	1 • 2 • 3 • 4 • 5 • 6	Followed by Problem 4
All IMO Problems and Solutions

Page

Toolbox

Search

1998 IMO Problems/Problem 3

Problem

Solution

See Also