Maths Olympiad Prep

Track / Stage 6 / 242 of 400 #1722 of 2444

Problem 1722

National Olympiad, first round
Number theory Difficulty 6.4 Prove it Korean Mathematical Olympiad · South Korea

A positive integer NN is said to be an "*n*-good number" if it satisfies the following two properties:
(Property 1) NN is divisible by at least nn distinct primes
(Property 2) There exist distinct positive divisors 1,x2,,xn1, x_2, \dots, x_n of NN such that
1+x2++xn=N. 1 + x_2 + \dots + x_n = N.
Show that there exists an "*n*-good number" for each n6n \ge 6.

This one wants a proof. Work it on paper, then read the official solution and mark yourself. Be honest about it: the record is only any use to you if it is.

Next problem →

Official solution

We use an induction on nn.

a. For n=6n = 6, put N6=237431807=18061807N_6 = 2 \cdot 3 \cdot 7 \cdot 43 \cdot 1807 = 1806 \cdot 1807. Since 1807=131391807 = 13 \cdot 139, N6N_6 is divisible by 6 distinct primes.
Moreover, since
1m=1m+1+1m(m+1), \frac{1}{m} = \frac{1}{m+1} + \frac{1}{m(m+1)},
we have

1=12+12=12+13+16=12+13+17+142=12+13+17+143+11806,(4243=1806)=12+13+17+143+11807+1N6. \begin{align*} 1 &= \frac{1}{2} + \frac{1}{2} \\ &= \frac{1}{2} + \frac{1}{3} + \frac{1}{6} \\ &= \frac{1}{2} + \frac{1}{3} + \frac{1}{7} + \frac{1}{42} \\ &= \frac{1}{2} + \frac{1}{3} + \frac{1}{7} + \frac{1}{43} + \frac{1}{1806}, \quad (42 \cdot 43 = 1806) \\ &= \frac{1}{2} + \frac{1}{3} + \frac{1}{7} + \frac{1}{43} + \frac{1}{1807} + \frac{1}{N_6}. \end{align*}
Hence, by multiplying both sides of above equality by N6N_6, we get
N6=1+N62+N63+N67+N643+N61807, N_6 = 1 + \frac{N_6}{2} + \frac{N_6}{3} + \frac{N_6}{7} + \frac{N_6}{43} + \frac{N_6}{1807},
where each term of the right hand side is a divisor of N6N_6.

b. Suppose there is an nn-good number NnN_n. Put
Nn+1=Nn(Nn+1). N_{n+1} = N_n(N_n + 1).
Then
Nn+1=(1+x2++xn)(Nn+1)=1+Nn+x2(Nn+1)++xn(Nn+1). \begin{align*} N_{n+1} &= (1 + x_2 + \cdots + x_n)(N_n + 1) \\ &= 1 + N_n + x_2(N_n + 1) + \cdots + x_n(N_n + 1). \end{align*}
Hence Nn+1N_{n+1} is a sum of n+1n+1 distinct divisors.
Since (Nn,Nn+1)=1(N_n, N_n + 1) = 1, prime divisors of Nn+1N_n + 1 are different from those of NnN_n. Since Nn+1N_n + 1 has at least one prime divisor, and since NnN_n has at least nn distinct prime divisors, Nn+1N_{n+1} has at least n+1n+1 distinct prime divisors. Therefore Nn+1N_{n+1} is a (n+1)(n+1)-good number. \square

Source: MathNet, licensed CC-BY-4.0. Statement reproduced verbatim; metadata (topic, difficulty, ordering) added by this project.