Maths Olympiad Prep

Library / /13 of 38

Number theory Difficulty 6.5 National olympiad Prove it China

For any integer nn with n>1n > 1, let
D(n)={aba,b are positive integers with n=ab and a>b}. D(n) = \{a - b \mid a, b \text{ are positive integers with } n = ab \text{ and } a > b\}.
Prove that for any integer kk with k>1k > 1, there exist kk pairwise distinct integers n1,n2,,nkn_1, n_2, \dots, n_k with ni>1 (1ik)n_i > 1\ (1 \le i \le k), such that D(n1)D(n2)D(nk)D(n_1) \cap D(n_2) \cap \dots \cap D(n_k) has at least two elements.

Solution

Proof. Let a1,a2,,ak+1a_1, a_2, \dots, a_{k+1} be k+1k+1 distinct positive integers, where each of them is smaller than the product of other kk numbers. Write N=a1a2ak+1N = a_1 a_2 \cdots a_{k+1}. For each i=1,2,,k+1i = 1, 2, \dots, k+1, let xi=12(Nai+ai)x_i = \frac{1}{2} \left( \frac{N}{a_i} + a_i \right), yi=12(Naiai)y_i = \frac{1}{2} \left( \frac{N}{a_i} - a_i \right), then xi2yi2=Nx_i^2 - y_i^2 = N.
Since aiaj<Na_i a_j < N and Nai>ai\frac{N}{a_i} > a_i, (xi,yi)(1ik+1)(x_i, y_i)(1 \le i \le k+1) are k+1k+1 positive integer solutions of equation x2y2=Nx^2 - y^2 = N. Without loss of generality, suppose xk+1=min{x1,x2,,xk+1}x_{k+1} = \min\{x_1, x_2, \dots, x_{k+1}\}. For each i{1,2,,k}i \in \{1, 2, \dots, k\}, since xi2yi2=xk+12yk+12x_i^2 - y_i^2 = x_{k+1}^2 - y_{k+1}^2, we have
(xi+xk+1)(xixk+1)=xi2xk+12=yi2yk+12=(yi+yk+1)(yiyk+1). (x_i + x_{k+1})(x_i - x_{k+1}) = x_i^2 - x_{k+1}^2 = y_i^2 - y_{k+1}^2 = (y_i + y_{k+1})(y_i - y_{k+1}).
Let ni=(xi+xk+1)(xixk+1)=(yi+yk+1)(yiyk+1)n_i = (x_i + x_{k+1})(x_i - x_{k+1}) = (y_i + y_{k+1})(y_i - y_{k+1}), then
2xk+1=(xi+xk+1)(xixk+1)D(ni), 2x_{k+1} = (x_i + x_{k+1}) - (x_i - x_{k+1}) \in D(n_i),
2yk+1=(yi+yk+1)(yiyk+1)D(ni). 2y_{k+1} = (y_i + y_{k+1}) - (y_i - y_{k+1}) \in D(n_i).
So xk+1>yk+1x_{k+1} > y_{k+1}, 2xk+12x_{k+1} and 2yk+12y_{k+1} are two different members of D(n1)D(n2)D(nk)D(n_1) \cap D(n_2) \cap \dots \cap D(n_k). \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.