Maths Olympiad Prep

Library / /57 of 97

Number theory Difficulty 8.1 Shortlist Prove it China

Let kk be a fixed odd integer, k>3k > 3. Prove: There exist infinitely many positive integers nn, such that there are two positive integers d1,d2d_1, d_2 satisfying d1,d2d_1, d_2 each dividing n2+12\frac{n^2+1}{2}, and d1+d2=n+kd_1 + d_2 = n + k.

Solution

((k2)2+1)xy=(x+yk)2+1,1 ((k-2)^2 + 1)xy = (x + y - k)^2 + 1, \qquad \textcircled{1}
we prove ① has infinitely many positive odd solutions (x,y)(x, y).
Obviously (1,1)(1,1) is one positive odd solution, let (x1,y1)=(1,1)(x_1, y_1) = (1,1). Assume (xi,yi)(x_i, y_i) is one positive odd solution of ①, and xiyix_i \le y_i, let xi+1=yix_{i+1} = y_i, yi+1=(k1)(k3)yi+2kxiy_{i+1} = (k-1)(k-3)y_i + 2k - x_i. Since ① can be written as
x2((k1)(k3)y+2k)x+(yk)2+1=0, x^2 - ((k-1)(k-3)y + 2k)x + (y-k)^2 + 1 = 0,
by Vieta's theorem (xi+1,yi+1)(x_{i+1}, y_{i+1}) is also one integer solution of ①. Since xi,yix_i, y_i and kk are all positive odd integers, and k5k \ge 5, so xi+1x_{i+1} is a positive odd integer, and
yi+1=(k1)(k3)yi+2kxixi1(mod2), y_{i+1} = (k-1)(k-3)y_i + 2k - x_i \equiv -x_i \equiv 1 \pmod{2},
yi+18yi+2kxi>yi>0y_{i+1} \ge 8y_i + 2k - x_i > y_i > 0. Thus (xi+1,yi+1)(x_{i+1}, y_{i+1}) is one positive odd solution of ①, and xi+yi<xi+1+yi+1x_i + y_i < x_{i+1} + y_{i+1}. By (x1,y1)(x_1, y_1) and the construction above, we get a series of positive odd solutions of ①: (xi,yi)(x_i, y_i), i=1,2,i=1,2,\dots, such that x1+y1<x2+y2<x_1 + y_1 < x_2 + y_2 < \dots.
For any integer ii greater than kk, xi+yi>kx_i + y_i > k. Let n=xi+yikn = x_i + y_i - k, d1=xid_1 = x_i, d2=yid_2 = y_i, then nn is a positive odd integer, and d1+d2=n+kd_1 + d_2 = n + k. Since (k2)2+1(k-2)^2 + 1 is even, we can show that d1,d2d_1, d_2 are both divisors of n2+12\frac{n^2+1}{2}, and d1+d2=n+kd_1 + d_2 = n + k. Thus such nn satisfies all the conditions, therefore there exist infinitely many positive odd integers nn satisfying the conditions.

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.