Maths Olympiad Prep

Library / /45 of 101

Number theory Difficulty 6.0 National olympiad Prove it Estonia

A positive integer mm is called usual if the square of every prime divisor of mm is less than mm.

a. Prove that there are infinitely many positive integers nn such that both nn and n+1n+1 are usual.

b. Is there a positive integer nn such that nn, n+1n+1 and n+2n+2 are all usual?

Solutions — 2

Solution 1

Let aa be a composite number such that a+1a+1 is composite, too. Then a2a^2 is usual since each of its prime divisors is a prime divisor of aa and therefore less than aa. We show that a21a^2-1 is usual, too. To this end, observe that a21=(a1)(a+1)a^2-1 = (a-1)(a+1). As a+1a+1 is composite, all prime divisors of a+1a+1 are less than a+1a+1. But as the difference of a+1a+1 and its arbitrary prime divisor is also divisible by this divisor, the prime divisors of a+1a+1 cannot be larger than a1a-1. Thus no prime divisor of a21a^2-1 is larger than a1a-1, meaning that the squares of prime divisors of a21a^2-1 do not exceed (a1)2(a-1)^2. As (a21)(a1)2=(a1)((a+1)(a1))=2(a1)>0(a^2-1) - (a-1)^2 = (a-1)((a+1) - (a-1)) = 2(a-1) > 0, squares of prime divisors of a21a^2-1 are less than a21a^2-1, implying that a21a^2-1 is usual. Consequently, n=a21n = a^2-1 is a suitable example.
As there exist arbitrarily long sequences of consecutive composite numbers, one can choose two consecutive composite numbers in infinitely many ways. Hence there exist infinitely many integers with the desired property. It remains to notice that a=21a = 21 implies a2+1=442=21317a^2 + 1 = 442 = 2 \cdot 13 \cdot 17, whereas 22<132<172=289<4422^2 < 13^2 < 17^2 = 289 < 442. Hence (440, 441, 442) is a triple of consecutive positive integers, all of which are usual.

Solution 2

Consider the so-called Pell's equation x22y2=1x^2 - 2y^2 = 1. It has the trivial solution (x0,y0)=(1,0)(x_0, y_0) = (1, 0), and whenever (xk1,yk1)(x_{k-1}, y_{k-1}) is a solution, (xk,yk)=(3xk1+4yk1,2xk1+3yk1)(x_k, y_k) = (3x_{k-1} + 4y_{k-1}, 2x_{k-1} + 3y_{k-1}) is a solution, too.
As x0<x1<x2<x_0 < x_1 < x_2 < \dots and y0<y1<y2<y_0 < y_1 < y_2 < \dots, all these solutions are distinct. Note that 3y03 \mid y_0 and, whenever 3y2k3 \mid y_{2k}, also 33x2k+4y2k=x2k+13 \mid 3x_{2k} + 4y_{2k} = x_{2k+1}, and whenever 3x2k+13 \mid x_{2k+1}, also 32x2k+1+3y2k+1=y2k+23 \mid 2x_{2k+1} + 3y_{2k+1} = y_{2k+2}. Hence 3x2k+13 \mid x_{2k+1} for every natural number kk.
Let kk be any positive integer. We show that n=2y2k+12n = 2y_{2k+1}^2 meets the conditions. To this end, let pp be any prime divisor of nn. If p>2p > 2 then py2k+12p \mid y_{2k+1}^2, implying py2k+1p \mid y_{2k+1} which gives py2k+1p \le y_{2k+1}. But if p=2p = 2 then p=y1<y2k+1p = y_1 < y_{2k+1} still. Thus p2y2k+12<2y2k+12=np^2 \le y_{2k+1}^2 < 2y_{2k+1}^2 = n in any case. Let pp now be a prime divisor of n+1=x2k+12n+1 = x_{2k+1}^2. Then also px2k+1p \mid x_{2k+1}. We previously showed that 3x2k+13 \mid x_{2k+1}. As 3=x1<x2k+13 = x_1 < x_{2k+1}, the number x2k+1x_{2k+1} is composite, implying that p<x2k+1p < x_{2k+1}. Thus p2<x2k+12=n+1p^2 < x_{2k+1}^2 = n+1. Consequently, nn and n+1n+1 are both usual. This solves part (a) of the problem since the parameter kk can be chosen in infinitely many ways which all produce different solutions.
To solve part (b), it suffices to note that if k=1k = 1 then n=2702=9800n = 2 \cdot 70^2 = 9800, n+1=992=9801n+1 = 99^2 = 9801 and n+2=9802=213229n+2 = 9802 = 2 \cdot 13^2 \cdot 29. Moreover, observe that 22<132<292=841<98022^2 < 13^2 < 29^2 = 841 < 9802. Hence 9800, 9801 and 9802 are three consecutive positive integers which are all usual.

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.