Maths Olympiad Prep

Library / /39 of 61

Number theory Difficulty 6.5 National olympiad Prove it Belarus

For a fixed integer n2n \ge 2 consider the sequence
ak=lcm(k,k+1,,k+(n1)). a_k = \text{lcm}(k, k+1, \dots, k+(n-1)).
Find all integers n2n \ge 2 for which the sequence aka_k increases starting from some number.

Solution

Answer: n=2n = 2.

Note that if n=2n = 2, the sequence has the form ak=k(k+1)a_k = k(k+1) since consecutive numbers are always coprime. It is clear that k(k+1)<(k+1)(k+2)k(k+1) < (k+1)(k+2), so the sequence is increasing.

First solution. Let us show that if n3n \geq 3 the sequence is not increasing from any number. Choose k=npk = np where pp is an arbitrary prime number greater than nn. All numbers np+1,np+2,,np+n1np+1, np+2, \dots, np+n-1 are not divisible by pp and there is at least one even among them. The number n(p+1)n(p+1) is also not divisible by pp and p+1p+1 is even. Hence
ak=plcm(n,np+1,np+2,,np+n1),ak+1p+12lcm(n,np+1,np+2,,np+n1). a_k = p \cdot \text{lcm}(n, np+1, np+2, \dots, np+n-1), \\ a_{k+1} \le \frac{p+1}{2} \cdot \text{lcm}(n, np+1, np+2, \dots, np+n-1).
Therefore ak>ak+1a_k > a_{k+1} for kk large enough and the sequence aka_k is not increasing from any number.

Second solution. We will show how else one can prove that for n3n \geq 3 the sequence is not increasing from any moment. Suppose that aka_k is increasing from number k0k_0 then for all kk0k \geq k_0 holds ak+1aka_{k+1} \geq a_k. Consider k=m!nk = m! - n where m>max(n!+n,k0)m > \max(n! + n, k_0).

Denote lcm(k+1,,k+n1)\text{lcm}(k+1, \dots, k+n-1) by NN. Then the inequality ak+1aka_{k+1} \ge a_k is equivalent to lcm(N,m!)>lcm(m!n,N)\text{lcm}(N, m!) > \text{lcm}(m! - n, N). Using the well known equality lcm(a,b)gcd(a,b)=ab\text{lcm}(a, b) \cdot \text{gcd}(a, b) = a \cdot b we obtain the equivalence:
lcm(N,m!)>lcm(m!n,N)    Nm!gcd(N,m!)>(m!n)Ngcd(m!n,N), \text{lcm}(N, m!) > \text{lcm}(m! - n, N) \iff \frac{N \cdot m!}{\text{gcd}(N, m!)} > \frac{(m! - n) \cdot N}{\text{gcd}(m! - n, N)},
or, after equivalent transformations,
ngcd(N,m!)>m!(gcd(N,m!)gcd(m!n,N)).(1) n \cdot \text{gcd}(N, m!) > m! \cdot (\text{gcd}(N, m!) - \text{gcd}(m! - n, N)). \quad (1)
It is clear that gcd(m!,m!l)=gcd(m!,l)=l\text{gcd}(m!, m! - l) = \text{gcd}(m!, l) = l for all ll from 11 to n1n-1, hence (n1)!gcd(N,m!)lcm(1,2,,n1)(n-1)! \ge \text{gcd}(N, m!) \ge \text{lcm}(1, 2, \dots, n-1). Moreover, since m!m! is divisible by ll, the number gcd(m!n,m!n+l)=gcd(n,nl)\text{gcd}(m! - n, m! - n + l) = \text{gcd}(n, n-l) is a divisor of nn. So the number gcd(m!n,N)\text{gcd}(m! - n, N) is a divisor of nn too. Indeed νp(N)=max(νp(m!n+1),,νp(m!n+(n1)))\nu_p(N) = \max(\nu_p(m! - n + 1), \dots, \nu_p(m! - n + (n-1))) for any prime divisor pp of NN.
From obtained inequalities and (1) it follows that
n(n1)!>m!(lcm(1,2,,n1)n).(2) n \cdot (n-1)! > m! \cdot (\text{lcm}(1, 2, \dots, n-1) - n). \quad (2)
Since lcm(1,2,,n1)(n2)(n1)\text{lcm}(1, 2, \dots, n-1) \ge (n-2)(n-1), for n4n \ge 4 the right hand side of (2) is not less than m!m! whence n!>m!n! > m!, a contradiction.
If n=3n=3 then gcd(N,m!)=gcd(m!2,m!)=2\text{gcd}(N, m!) = \text{gcd}(m! - 2, m!) = 2. But
gcd(m!n,N)=gcd(m!3,(m!2)(m!1))=1, \text{gcd}(m! - n, N) = \text{gcd}(m! - 3, (m! - 2)(m! - 1)) = 1,
so the inequality (1) will become 6>m!6 > m! which is wrong.

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.