1998 IMO Problems/Problem 3
Problem
For any positive integer , let denote the number of positive divisors of (including 1 and itself). Determine all positive integers such that for some .
Solution
First we must etermine generl values for : Let , if is an aritrry divisor of then must have the same prime factors of , each with an exponent being: . Hence there are choices for each exponent of Pi in the number d => there are such d
where are exponents of the prime numbers in the prime factorisation of .
So we want to find all integers that can e represented by the product of fractions of the form Obviously is odd as the numerator is always odd. It's possible for 1 (1/1) and 3 , which suggests that it may be possible for all odd integers, which we can show by induction.
: It's possible to represent as the product of fractions
Base case: Now assume that for it's possible for all odds < .
Since is odd, where is odd and <
Let there be a number s.t
Also consider . It is sufficient to show that can be represented by a product of fractions of the form in order to show can be represented by product of fractions , since can be represented in such a manner too.
Using our definition of in terms of :
And that is simply the product of fractions: .
We have shown that can be written s.t it's a product of fractions of the form can be written in such a way too.
Hence we have shown that all odds less than satisfies is true. Since we have shown P(1) is true, it must hence be true for all odd integers.
Therefore, is odd, for some n. I.E all odd satisfy the condition posed in the question.∎
-dabab_kebab (wrote this solution)
See Also
1998 IMO (Problems) • Resources | ||
Preceded by Problem 2 |
1 • 2 • 3 • 4 • 5 • 6 | Followed by Problem 4 |
All IMO Problems and Solutions |