Number theoryDifficulty 6.1National OlympiadProve itIran
Let n>1 be an integer. Prove that there exists an integer n−1≥m≥⌊2n⌋ such that the following equation has integer solutions with am>0 m+1am+m+2am+1+⋯+nan−1=lcm(1,2,…,n)1.
Solution
Two simple lemmas are needed to prove the problem.
Lemma. For all integers k>1, if x1,x2,…,xk are integers with gcd(x1,…,xk)=1, then there are integers a1,…,ak such that a1x1+⋯+akxk=1.
Proof. For k=2 the statement of the lemma is Bézout's Lemma for relatively prime numbers, that is well-known. Now we use induction on k. Knowing that the lemma is true for k=n, for numbers x1,…,xn+1 that are relatively prime, we have gcd(x1,x2,…,xn−1,gcd(xn,xn+1))=1. Now applying the lemma for k=n, there are numbers a1,…,an such that a1x1+a2x2+⋯+an−1xn−1+angcd(xn,xn+1)=1 Using the Bézout's Lemma, there are bn,bn+1 such that gcd(xn,xn+1)=bnxn+bn+1xn+1. Set yi=ai for i<n, yn=anbn and yn+1=anbn+1 to get y1x1+⋯+yn+1xn+1=1. Which is the statement of the lemma for k=n+1. So the lemma is proved using induction.
Lemma.SetL=lcm(1,2,…,n), then gcd(m+1L,m+2L,…,nL)=1 where m=⌊2n⌋.
Proof. First note that lcm(1,2,…,n)=lcm(m+1,m+2,…,n). That is because for all 1≤k≤m, the number s=⌈log2(km+1)⌉ is an integer such that 2s⋅k∈{m+1,m+2,…,n}. Now assume that d=gcd(m+1L,m+2L,…,nL). For all m+1≤i≤n we have d∣iL⟹∃k;d⋅k=iL⟹i⋅k=dL⟹i∣dL. Which implies L=lcm(m+1,m+2,…,n)∣dL⟹d=1.
Back to the problem, according to both lemmas, since gcd(m+1L,m+2L,…,nL)=1, we obtain there are some integers xm,xm+1,…,xn−1 such that xm⋅m+1L+xm+1⋅m+2L+⋯+xn−1⋅nL=1. Now consider a natural number t such that xm+t⋅m+2L>0 and set ⎩⎨⎧am=xm+t⋅m+2L,am+1=xm+1−t⋅m+1L,ai=xi,∀i>m+1 to get m+1am+m+2am+1+⋯+nan−1=lcm(1,2,…,n)1. Since am=xm+t⋅m+2L>0, this is the desired equation for m=⌊2n⌋.
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.