Maths Olympiad Prep

Library / Belarusian Mathematical Olympiad /150 of 208

Belarusian Mathematical Olympiad

Number theory Difficulty 6.5 National Olympiad Prove it Belarus

For a fixed integer n≥2n \ge 2 consider the sequence
ak=lcm(k,k+1,…,k+(n−1)). a_k = \text{lcm}(k, k+1, \dots, k+(n-1)).
Find all integers n≥2n \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 n≥3n \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+n−1np+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=p⋅lcm(n,np+1,np+2,…,np+n−1),ak+1≤p+12⋅lcm(n,np+1,np+2,…,np+n−1). 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 n≥3n \geq 3 the sequence is not increasing from any moment. Suppose that aka_k is increasing from number k0k_0 then for all k≥k0k \geq k_0 holds ak+1≥aka_{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+n−1)\text{lcm}(k+1, \dots, k+n-1) by NN. Then the inequality ak+1≥aka_{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)=a⋅b\text{lcm}(a, b) \cdot \text{gcd}(a, b) = a \cdot b we obtain the equivalence:
lcm(N,m!)>lcm(m!−n,N)  ⟺  N⋅m!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,
n⋅gcd(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 n−1n-1, hence (n−1)!≥gcd(N,m!)≥lcm(1,2,…,n−1)(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,n−l)\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+(n−1)))\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⋅(n−1)!>m!⋅(lcm(1,2,…,n−1)−n).(2) n \cdot (n-1)! > m! \cdot (\text{lcm}(1, 2, \dots, n-1) - n). \quad (2)
Since lcm(1,2,…,n−1)≥(n−2)(n−1)\text{lcm}(1, 2, \dots, n-1) \ge (n-2)(n-1), for n≥4n \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,604 problems in a working order, from Junior Challenge level to the IMO shortlist.

Source: MathNet, licensed CC-BY-4.0. Statement reproduced verbatim; metadata (topic, difficulty) added by this project.