Maths Olympiad Prep

Library / /84 of 299

Number theory Difficulty 6.1 National Olympiad Prove it Iran

Let n>1n > 1 be an integer. Prove that there exists an integer n1mn2n-1 \ge m \ge \lfloor \frac{n}{2} \rfloor such that the following equation has integer solutions with am>0a_m > 0
amm+1+am+1m+2++an1n=1lcm(1,2,,n). \frac{a_m}{m+1} + \frac{a_{m+1}}{m+2} + \dots + \frac{a_{n-1}}{n} = \frac{1}{\text{lcm}(1, 2, \dots, n)}.

Solution

Two simple lemmas are needed to prove the problem.

Lemma. For all integers k>1k > 1, if x1,x2,,xkx_1, x_2, \dots, x_k are integers with
gcd(x1,,xk)=1, \gcd(x_1, \dots, x_k) = 1,
then there are integers a1,,aka_1, \dots, a_k such that
a1x1++akxk=1. a_1x_1 + \dots + a_kx_k = 1.

Proof. For k=2k = 2 the statement of the lemma is Bézout's Lemma for relatively prime numbers, that is well-known. Now we use induction on kk. Knowing that the lemma is true for k=nk = n, for numbers x1,,xn+1x_1, \dots, x_{n+1} that are relatively prime, we have
gcd(x1,x2,,xn1,gcd(xn,xn+1))=1. \text{gcd}(x_1, x_2, \dots, x_{n-1}, \text{gcd}(x_n, x_{n+1})) = 1.
Now applying the lemma for k=nk = n, there are numbers a1,,ana_1, \dots, a_n such that
a1x1+a2x2++an1xn1+angcd(xn,xn+1)=1 a_1x_1 + a_2x_2 + \dots + a_{n-1}x_{n-1} + a_n\text{gcd}(x_n, x_{n+1}) = 1
Using the Bézout's Lemma, there are bn,bn+1b_n, b_{n+1} such that
gcd(xn,xn+1)=bnxn+bn+1xn+1. \text{gcd}(x_n, x_{n+1}) = b_n x_n + b_{n+1} x_{n+1}.
Set yi=aiy_i = a_i for i<ni < n, yn=anbny_n = a_n b_n and yn+1=anbn+1y_{n+1} = a_n b_{n+1} to get
y1x1++yn+1xn+1=1. y_1 x_1 + \dots + y_{n+1} x_{n+1} = 1.
Which is the statement of the lemma for k=n+1k = n + 1. So the lemma is proved using induction.

Lemma. Set L=lcm(1,2,,n)L = \text{lcm}(1, 2, \dots, n), then gcd(Lm+1,Lm+2,,Ln)=1\text{gcd}(\frac{L}{m+1}, \frac{L}{m+2}, \dots, \frac{L}{n}) = 1 where m=n2m = \lfloor \frac{n}{2} \rfloor.

Proof. First note that lcm(1,2,,n)=lcm(m+1,m+2,,n)\text{lcm}(1, 2, \dots, n) = \text{lcm}(m+1, m+2, \dots, n). That is because for all 1km1 \le k \le m, the number s=log2(m+1k)s = \lceil \log_2(\frac{m+1}{k}) \rceil is an integer such that
2sk{m+1,m+2,,n}. 2^s \cdot k \in \{m+1, m+2, \dots, n\}.
Now assume that
d=gcd(Lm+1,Lm+2,,Ln). d = \text{gcd} \left( \frac{L}{m+1}, \frac{L}{m+2}, \dots, \frac{L}{n} \right).
For all m+1inm+1 \le i \le n we have
dLi    k;dk=Li    ik=Ld    iLd. d \mid \frac{L}{i} \implies \exists k; d \cdot k = \frac{L}{i} \implies i \cdot k = \frac{L}{d} \implies i \mid \frac{L}{d}.
Which implies
L=lcm(m+1,m+2,,n)Ld    d=1. L = \text{lcm}(m+1, m+2, \dots, n) \mid \frac{L}{d} \implies d = 1.

Back to the problem, according to both lemmas, since
gcd(Lm+1,Lm+2,,Ln)=1, \text{gcd} \left( \frac{L}{m+1}, \frac{L}{m+2}, \dots, \frac{L}{n} \right) = 1,
we obtain there are some integers xm,xm+1,,xn1x_m, x_{m+1}, \dots, x_{n-1} such that
xmLm+1+xm+1Lm+2++xn1Ln=1. x_m \cdot \frac{L}{m+1} + x_{m+1} \cdot \frac{L}{m+2} + \dots + x_{n-1} \cdot \frac{L}{n} = 1.
Now consider a natural number tt such that xm+tLm+2>0x_m + t \cdot \frac{L}{m+2} > 0 and set
{am=xm+tLm+2,am+1=xm+1tLm+1,ai=xi,i>m+1 \begin{cases} a_m = x_m + t \cdot \frac{L}{m+2}, \\ a_{m+1} = x_{m+1} - t \cdot \frac{L}{m+1}, \\ a_i = x_i, \end{cases} \quad \forall i > m+1
to get
amm+1+am+1m+2++an1n=1lcm(1,2,,n). \frac{a_m}{m+1} + \frac{a_{m+1}}{m+2} + \dots + \frac{a_{n-1}}{n} = \frac{1}{\text{lcm}(1, 2, \dots, n)}.
Since am=xm+tLm+2>0a_m = x_m + t \cdot \frac{L}{m+2} > 0, this is the desired equation for m=n2m = \lfloor \frac{n}{2} \rfloor.

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 reproduced verbatim; metadata (topic, difficulty) added by this project.