Maths Olympiad Prep

Library / /4 of 8

Number theory Difficulty 6.4 National olympiad Prove it 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.

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

Want a route through all this instead of an archive? The track puts 2,000 problems in a working order, from AMC 10 level to the IMO shortlist.

Source: MathNet, licensed CC-BY-4.0. Statement and solution reproduced as published; topic and difficulty added by this site.