Let $m,n$ be distinct positive integers. Prove that $$gcd(m,n) + gcd(m+1,n+1) + gcd(m+2,n+2) \le 2|m-n| + 1. $$Further, determine when equality holds.
Problem
Source:
Tags: number theory, MONT
20.01.2019 16:56
WLOG $m>n$. Let $k = m - n$, we have $LHS=\gcd(m,k)+\gcd(m+1,k)+\gcd(m+2,k)$ and $RHS = 2k+1$. If $k=1,2$ it is easy to see. If $k>2$, not all of the $\gcd$'s are equal to $k$. Therefore $\gcd(m,k)+\gcd(m+1,k)+\gcd(m+2,k)\leq k + \frac{k}2+\frac{k}2<2k+1~~~\square$ Equality holds for consecutive $m,n$; $m-n=2$ or $n-m=2$ and $m,n$ even.
20.01.2019 16:57
TheDarkPrince wrote: WLOG $m>n$. Let $k = m - n$, we have $LHS=\gcd(m,k)+\gcd(m+1,k)+\gcd(m+2,k)$ and $RHS = 2k+1$. If $k=1,2$ it is easy to see. If $k>2$, not all of the $\gcd$'s are equal to $k$. Therefore $\gcd(m,k)+\gcd(m+1,k)+\gcd(m+2,k)\leq k + \frac{k}2+\frac{k}2<2k+1~~~\square$ Equality holds for consecutive $m,n$; $m-n=2$ or $n-m=2$ and $m,n$ even. Did the same here
20.01.2019 17:00
Suppose $m>n$ $gcd(m,n)=x_1$ $gcd(m+1,n+1)=x_2$ $gcd(m+2,n+2)=x_3$ $x_1 \mid m-n$,$x_2 \mid m-n$,$x_3 \mid m-n$ We chose $M$=max${x_1,x_2,x_3}$ and we take another number from ${x_1,x_2,x_3}$ prime with $M$ note $M_1$ and the other one $M_2$.Now $2(m-n)+1 \le 2MM_1+1=MM_1+1+MM_1 \le (M+M_1)+M_2$ so the equality hold when $gcd(m+1,n+1)=1$ and $m-n=gcd(m,n)=gcd(m+2,n+2)$ so for $(m,n)=(2,4)$
20.01.2019 17:08
DanDumitrescu wrote: We chose $M=max{x_1,x_2,x_3}$ and we have another number from $max{x_1,x_2,x_3}$ prime with $M$ Didn't get you here.
20.01.2019 17:08
TheDarkPrince wrote: WLOG $m>n$. Let $k = m - n$, we have $LHS=\gcd(m,k)+\gcd(m+1,k)+\gcd(m+2,k)$ and $RHS = 2k+1$. If $k=1,2$ it is easy to see. If $k>2$, not all of the $\gcd$'s are equal to $k$. Therefore $\gcd(m,k)+\gcd(m+1,k)+\gcd(m+2,k)\leq k + \frac{k}2+\frac{k}2<2k+1~~~\square$ Equality holds for consecutive $m,n$; $m-n=2$ or $n-m=2$ and $m,n$ even. How can you write $LHS=\gcd(m,k)+\gcd(m+1,k)+\gcd(m+2,k)$
20.01.2019 17:11
Math-wiz wrote: TheDarkPrince wrote: WLOG $m>n$. Let $k = m - n$, we have $LHS=\gcd(m,k)+\gcd(m+1,k)+\gcd(m+2,k)$ and $RHS = 2k+1$. If $k=1,2$ it is easy to see. If $k>2$, not all of the $\gcd$'s are equal to $k$. Therefore $\gcd(m,k)+\gcd(m+1,k)+\gcd(m+2,k)\leq k + \frac{k}2+\frac{k}2<2k+1~~~\square$ Equality holds for consecutive $m,n$; $m-n=2$ or $n-m=2$ and $m,n$ even. How can you write $LHS=\gcd(m,k)+\gcd(m+1,k)+\gcd(m+2,k)$ $GCD(m,n) =GCD(m,m-n)$. Euclid's division lemma
20.01.2019 18:38
Can we state that gcd(x,t)+gcd(x,t+1)<x+1
20.01.2019 19:46
This problem was proposed by me My solution is similiar to TDPs.
20.01.2019 19:47
Supercali wrote: This problem was proposed by me How do you propose problems for INMO?
20.01.2019 20:41
Supercali wrote: This problem was proposed by me My solution is similiar to TDPs. Congrats! Really nice problem
21.01.2019 08:37
I did the same thing as TDP. Would anything be deducted if I didn't prove that (m, n) = (m, m-n)?
21.01.2019 10:38
scimaths wrote: I did the same thing as TDP. Would anything be deducted if I didn't prove that (m, n) = (m, m-n)? It its trivial from Euclid's division lemma.
21.01.2019 10:39
Supercali wrote: This problem was proposed by me My solution is similiar to TDPs. How does one propose problems for INMO?
21.01.2019 18:47
21.01.2019 19:02
enthusiast101 wrote:
Incorrect. If $gcd(m,k) = k$ then $gcd(m+2,k) = 2$ is also permissible, iff m and n are even. So TDP is right. Recommendation - if you find that you have abundant time and your answer doesn't match with that of someone else, it is nice to verify whether any of these solutions work for some particular cases or not.
22.01.2019 20:48
TheDarkPrince wrote: WLOG $m>n$. Let $k = m - n$, we have $LHS=\gcd(m,k)+\gcd(m+1,k)+\gcd(m+2,k)$ and $RHS = 2k+1$. If $k=1,2$ it is easy to see. If $k>2$, not all of the $\gcd$'s are equal to $k$. Therefore $\gcd(m,k)+\gcd(m+1,k)+\gcd(m+2,k)\leq k + \frac{k}2+\frac{k}2<2k+1~~~\square$ Equality holds for consecutive $m,n$; $m-n=2$ or $n-m=2$ and $m,n$ even. You have proved it( the general case ) for only less than 2k+1 but it must be proved for less than or equal to 2k+1; because even if you have taken k>2, still k can be even, then the general equation must satisfy less than or equal to 2k+1 and it will never satisfy your general equation which states it will be less than or equal to 2k (for example k is even doesn't satisfy less than 2k+1 it will always be equal to 2k+1). See where the contradiction comes. And if I'm saying this wrong then please explain it to me.
22.01.2019 20:52
^ I don't get what you are trying to say. Do you mean that if I can show $1<3$, then $1\leq 3$ isn't true?
23.01.2019 09:50
Ditzymathstar wrote: TheDarkPrince wrote: WLOG $m>n$. Let $k = m - n$, we have $LHS=\gcd(m,k)+\gcd(m+1,k)+\gcd(m+2,k)$ and $RHS = 2k+1$. If $k=1,2$ it is easy to see. If $k>2$, not all of the $\gcd$'s are equal to $k$. Therefore $\gcd(m,k)+\gcd(m+1,k)+\gcd(m+2,k)\leq k + \frac{k}2+\frac{k}2<2k+1~~~\square$ Equality holds for consecutive $m,n$; $m-n=2$ or $n-m=2$ and $m,n$ even. You have proved it( the general case ) for only less than 2k+1 but it must be proved for less than or equal to 2k+1; because even if you have taken k>2, still k can be even, then the general equation must satisfy less than or equal to 2k+1 and it will never satisfy your general equation which states it will be less than or equal to 2k (for example k is even doesn't satisfy less than 2k+1 it will always be equal to 2k+1). See where the contradiction comes. And if I'm saying this wrong then please explain it to me. The given solution is correct as equality only occurs when k is 1 or 2. So for k>2 the inequality must be strict.
23.01.2019 19:51
Ditzymathstar wrote: TheDarkPrince wrote: WLOG $m>n$. Let $k = m - n$, we have $LHS=\gcd(m,k)+\gcd(m+1,k)+\gcd(m+2,k)$ and $RHS = 2k+1$. If $k=1,2$ it is easy to see. If $k>2$, not all of the $\gcd$'s are equal to $k$. Therefore $\gcd(m,k)+\gcd(m+1,k)+\gcd(m+2,k)\leq k + \frac{k}2+\frac{k}2<2k+1~~~\square$ Equality holds for consecutive $m,n$; $m-n=2$ or $n-m=2$ and $m,n$ even. You have proved it( the general case ) for only less than 2k+1 but it must be proved for less than or equal to 2k+1; because even if you have taken k>2, still k can be even, then the general equation must satisfy less than or equal to 2k+1 and it will never satisfy your general equation which states it will be less than or equal to 2k (for example k is even doesn't satisfy less than 2k+1 it will always be equal to 2k+1). See where the contradiction comes. And if I'm saying this wrong then please explain it to me. He has only written some lines of calculation for the case where equality doesn't hold. But I think even before that he mentioned the cases where equality always holds, saying that it is easy to see. I think you rushed while reading it, didn't yo
25.01.2019 11:26
MathPassionForever wrote: Ditzymathstar wrote: TheDarkPrince wrote: WLOG $m>n$. Let $k = m - n$, we have $LHS=\gcd(m,k)+\gcd(m+1,k)+\gcd(m+2,k)$ and $RHS = 2k+1$. If $k=1,2$ it is easy to see. If $k>2$, not all of the $\gcd$'s are equal to $k$. Therefore $\gcd(m,k)+\gcd(m+1,k)+\gcd(m+2,k)\leq k + \frac{k}2+\frac{k}2<2k+1~~~\square$ Equality holds for consecutive $m,n$; $m-n=2$ or $n-m=2$ and $m,n$ even. You have proved it( the general case ) for only less than 2k+1 but it must be proved for less than or equal to 2k+1; because even if you have taken k>2, still k can be even, then the general equation must satisfy less than or equal to 2k+1 and it will never satisfy your general equation which states it will be less than or equal to 2k (for example k is even doesn't satisfy less than 2k+1 it will always be equal to 2k+1). See where the contradiction comes. And if I'm saying this wrong then please explain it to me. He has only written some lines of calculation for the case where equality doesn't hold. But I think even before that he mentioned the cases where equality always holds, saying that it is easy to see. I think you rushed while reading it, didn't yo I believe I must have done what you've said. But still thank you guys for clearing my doubt . I really didn't understand it before..
28.01.2019 18:08
For all naturals $n,k$, we have $$\gcd(n,k)+\gcd(n+1,k) \le 1+k $$Indeed, $$\gcd(n,k)+\gcd(n+1,k) \le 1+\gcd(n,k) \cdot \gcd(n+1,k) = 1+\gcd(n(n+1),k) \le 1+k$$ So if $m<n$ and $k=n-m$, then the LHS is equal to $$\gcd(n,k)+\gcd(n+1,k)+\gcd(n+2,k)\le 2+2k-\gcd(n+1,k)\le 2k+1$$as required. Equality holds iff $\gcd(n+1,k)=1, \gcd(n,k)=k,$ and $\gcd(n+2,k)=k$, from which it is not hard to deduce that the only $(m,n)$ that work are either those with difference $1$ or even numbers with difference $2$.
08.02.2019 09:47
let us suppose that $(m, n)$ be even and odd then let us suppose that they are of the form $4k=m$ ,$k>0$ and $n=6k+1$ ,$k>0$ Then we may apply $(m, n) =(m, n–m) $,$n>m$ $gcd(m,n)+gcd(m+1,n+1)+gcd(m+2,n+2)$ $=gcd(4k,6k+1)+gcd(4k+1,6k+2)+gcd(4k+2,6k+3)$ $=gcd(2k–1,2k+1)+gcd(2k,2k+1)+gcd(4k+2,2k+1)$ $(4k+2,2k+1)=(2k+1,2k+1)=2k+1$ Thus the inequality reduces to Since $(2k–1,2k+1)=1,gcd(2k,2k+1)=1$ $1+1+2k+1\le 2|2k+1|+1$ $3+2k\le 4k+3$ $2k\ge 0$ which is obvious true $k>0$ Also $|m–n|=1,2$ are cases of equality Let $m=2k,n=4k$ then after reducing we will get $2k+1+2\le 4k+1$ $2k–2\ge 0$ $k\ge 1$. Which is true intact for$ k=1 $we get equality, $(m, n) =(2,4)$
16.04.2019 20:34
Math-wiz wrote: TheDarkPrince wrote: WLOG $m>n$. Let $k = m - n$, we have $LHS=\gcd(m,k)+\gcd(m+1,k)+\gcd(m+2,k)$ and $RHS = 2k+1$. If $k=1,2$ it is easy to see. If $k>2$, not all of the $\gcd$'s are equal to $k$. Therefore $\gcd(m,k)+\gcd(m+1,k)+\gcd(m+2,k)\leq k + \frac{k}2+\frac{k}2<2k+1~~~\square$ Equality holds for consecutive $m,n$; $m-n=2$ or $n-m=2$ and $m,n$ even. How can you write $LHS=\gcd(m,k)+\gcd(m+1,k)+\gcd(m+2,k)$ gcd(m,n) = gcd(m,m-n)=gcd(m,n-m) and so on.
25.09.2019 19:48
Did anyone notice this problem uses a similar concept as RMO 2014 Region 4 P3?
20.10.2019 09:20
TheDarkPrince wrote: WLOG $m>n$. Let $k = m - n$, we have $LHS=\gcd(m,k)+\gcd(m+1,k)+\gcd(m+2,k)$ and $RHS = 2k+1$. If $k=1,2$ it is easy to see. If $k>2$, not all of the $\gcd$'s are equal to $k$. Therefore $\gcd(m,k)+\gcd(m+1,k)+\gcd(m+2,k)\leq k + \frac{k}2+\frac{k}2<2k+1~~~\square$ Equality holds for consecutive $m,n$; $m-n=2$ or $n-m=2$ and $m,n$ even. Umm.. I did not understand the n>2 case. Like how did you arrive at the k+k/2+k/2 inequality. Please help.
20.10.2019 10:51
AdventuresinHenderland wrote: Umm.. I did not understand the n>2 case. Like how did you arrive at the k+k/2+k/2 inequality. Please help. At most one of $m,m+1,$ and $m+2$ can be a multiple of $k$. So the $\gcd$ of a non-multiple of $k$ with $k$ can be at most $\frac{k}{2}$.
09.01.2020 09:37
Case bash!!
19.01.2020 08:31
enthusiast101 wrote:
For k>2
25.03.2020 06:32
At first of all our claim is $\gcd(a,b)=\gcd(a,|a-b|)$. Suppose $d=\gcd (a,b) $ ,we must have $d\mid a,b$ and $d\mid |a-b|$.sice $d$ is greatest common devisor of $a,b$ so $\gcd (a,|a-b|)=\gcd(b,|a-b|) =d$. Now suppose $d_1=\gcd(m,n)=\gcd(m,|m-n|)$. $d_2=\gcd(m+1,n+1)=\gcd(m+1,|m-n|)$ and finally $d_3=\gcd (m+2,n+2)=\gcd(m+2,|m-n|)$. If $d_1,d_2,d_3$ are $1$ then we are done . So we must look into cases when $d_1,d_2,d_3>1$. I claim that $d_1\neq d_2$ and hence $d_2 \neq d_3$. Suppose $d_1=d_2$ which implies $d_1|m+n$ and $d_1\mid m+n+2 $ which means $d_1\mid 2$ it forces that $d_1=d_2= 1$ but if never we get pairity of $m,m+1$ are same which is contradiction !!!! Similarly $d_2\neq d_3$. One case may come that $d_1=d_3$.(It's easy to note that it will be possible iff $d_1=d_3=2$) In this case we must get $d_1+d_2+d_3\le \frac{ |m-n|}{2}+4 $ which also follow the conclusion! Now we look Where $d_1\neq d_3$ Indeed we have $d_1,d_2,d_3\mid |m-n|$. So it is obvious that $d_1+d_2+d_3 \le \frac{|m-n|}{3}+\frac{|m-n|}{2}+|m-n|<2|m-n|+1$. Now iff $m=2k,n=2k+2$ then $d_1+d_2+d_3= 2+2+1$ which is equal to $2|m-n|+1$. So equality occurs iff $m,n$ are consecutive even or any cosecutive integer.
08.02.2021 15:39
Trivial Lemma-: if $a>b$ then $gcd(a, b)\leq b$ FTSOC assume $k>b$ where $gcd(a, b)=k$ and then we will have $b=kx_1$ for some $x_1\in N$ our assumption is wrong. So $k\leq b$. Now observe By Euclid Division Algorithm we have $gcd(m, n) +gcd(m+1, n+1)+gcd(m+2, n+2)=$ $gcd(m, n-m)+gcd(m+1, n-m)+gcd(m+2, n-m)+gcd(m+2, n-m)$ WLOG $n>m$ then Case 1-: Let $n-m\geq 2m$ or $n-m\geq 2m+1$ then by above Lemma we have $gcd(m, n-m)\leq m$ and $gcd(m+1, n-m)\leq m+1$ and $gcd(m+2, n-m)\leq m+2$ which when added gives $gcd(m, n-m)+gcd(m+1, n-m)+gcd(m+2, n-m)\leq m+m+1+m+2=3(m+1)\leq 2(n-m)+1$ Case 2-: if $m<n<2m$ then by lemma $gcd(m, n-m)\leq n-m$ and if is maximised then $gcd(m+1, n-m)=1, gcd(m+2, n-m) \leq 2$ then also we have $gcd(m, n-m)+gcd(m+1, n-m)+gcd(m+2, n-m)\leq n-m+1+2 \leq 2(n-m)+1$ hence $gcd(m, n) +gcd(m+1, n+1)+gcd(m+2, n+2)\leq 2|n-m|+1$ $\blacksquare$
14.02.2021 13:28
17.12.2021 09:02
10.05.2022 08:46
WLOG let $\ell=m-n>0.$ Suppose FTSOC that the inequality is false; then, $\ell/2+\ell/2+\ell/2<2\ell+1,$ so at least one of $a_i=\gcd(\ell,n+i)$ for $i=0,1,2$ is equal to $\ell.$ Case 1: $a_0=\ell.$ Then, $a_1=\gcd(\ell,n+1)=\gcd(\ell,1)=1$ and $a_2=\gcd(\ell,n+2)=\gcd(\ell,2)=1,2$ (if $m,n$ even, then $a_2=2.$ Else, $a_2=1$) by the Euclidean Algorithm. Hence, the inequality holds with equality when $\ell+2=2\ell+1$ or $\ell+3=2\ell+1$ and $m,n$ even. This is equivalent to $m,n$ being consecutive integers of $m,n$ being consecutive evens. Case 2: $a_1=\ell.$ Then, $a_0=a_2=1,$ so the inequality holds with equality when $\ell+2=2\ell+1,$ or $\ell=1.$ Case 3: $a_2=\ell.$ Then, $a_1=1$ and $a_0=1,2,$ (the latter if $m,n$ are even), so the inequality holds. We have similar equality cases to case one. Hence, the inequality is true with equality when $m,n$ are consecutive or when $m,n$ are consecutive evens. $\square$
06.12.2022 20:51
finally got around to writing up this problem The pith of the problem is the following claim. Claim: For any two positive integers $n$ and $k$, $$\gcd(k, n) + \gcd(k, n + 1) + \gcd(k, n + 2) \leqslant 2k + 1$$with equality holding if and only if: $k = 1$ and $n$ be any positive integer, $k = 2$ and $n$ be even. Proof. First, we define $g_0 = \gcd(k, n)$, $g_1 = \gcd(k, n + 1)$, $g_2 = \gcd(k, n + 2)$. Then, $\gcd(g_0, g_1) = \gcd(k, n, n + 1) = 1$, $\gcd(g_1, g_2) = \gcd(k, n + 1, n + 2) = 1$, and $\gcd(g_0, g_2) = \gcd(k, n, n + 2)$. Now, here we take two cases: Case #1: At least one of $k$ and $n$ is odd. Then, we have $\gcd(g_0, g_2) = 1$. Thus, $g_0, g_1, g_2$ are pairwise coprime to each other. Thus, since $g_0 \mid k, g_1 \mid k, g_2 \mid k$, we have that $g_0g_1g_2 \mid k$, which means $g_0g_1g_2 \leqslant k$. Now, we have another sub-claim. Sub-claim 1: If $a, b, c$ be positive integers, then $a + b + c \leqslant 2abc + 1$. Proof of sub-claim. This is equivalent to $\frac{1}{ab} + \frac{1}{bc} + \frac{1}{ca} \leqslant 2 + \frac{1}{abc}$. If $a, b, c > 1$, then the inequality is obvious. If one of them, say $a$ is $1$, then we have $$\Longleftrightarrow \frac{1}{b} + \frac{1}{c} \leqslant 2,$$which is obviously true since $a, b, c \geqslant 1$. In particular, equality holds if and only if $a = b = c = 1$. Now, by our subclaim, $g_0 + g_1 + g_2 \leqslant 2g_0g_1g_2 + 1 \leqslant 2k + 1$, so we are done for this case. Also, equality holds if and only if $g_1 = g_2 = g_3 = k = 1$, which can be checked that they all hold at once. Thus, equality holds here iff $k = 1$. Case #2: Both $k$ and $n$ are even. Then, we have $\gcd(g_0, g_2) = 2$. Take $g_0 = 2g_0'$, and $g_2 = 2g_2'$ with $\gcd(g_0', g_2') = 1$. Then, we have another sub-claim. Thus, $2g_0'g_1g_2' \mid k$. In particular, $2g_0'g_1g_2' \leqslant k$. Sub-claim 2: If $a, b, c$ be positive integers, then $2a + b + 2c \leqslant 4abc + 1$. Proof of sub-claim. This is equivalent to $\frac{2}{bc} + \frac{1}{ca} + \frac{2}{ab} \leqslant 4 + \frac{1}{abc}$. If $a, b, c > 1$, then the inequality is obvious. If $a = 1$, then the inequality is equivalent to $\frac{2}{bc} + \frac{1}{c} + \frac{2}{b} \leqslant 4 + \frac{1}{bc}$, which is equivalent to $\frac{1}{c} + \frac{2}{b} + \frac{1}{bc} \leqslant 4$, which is obviously true since $a, b, c \geqslant 1$. If $b = 1$, then the inequality is equivalent to $\frac{2}{a} + \frac{2}{b} \leqslant 4$, which is obviously true since $a, b, c \geqslant 1$. In particular, equality holds iff $a = b = c = 1$. Now, we have $2g_0' + g_1 + 2g_2' \leqslant 4g_0'g_1g_2' + 1 \leqslant 2k + 1$, with equality holding iff $g_0' = g_1 = g_2' = 1, k = 2g_0'g_1g_2'$, which is equivalent to $g_0 = 2, g_1 = 1, g_2 = 2, k = 2$. We can check that all these conditions are satisfied together for even $n$. In conclusion, equality holds if $k = 1$, $n$ being any positive integer or when $k = 2$, and $n$ even. Now, we move to the main problem. Note that $\gcd(m + i, n + i) = \gcd(|m - n|, n + i)$, which means that our sum simplifies to $$\gcd(k, n) + \gcd(k, n + 1) + \gcd(k, n + 2) \leqslant 2k + 1,$$where $k = |m - n|$, which is exactly what we proved in the above claim. Also, equality holds iff $|m - n| = 1$, and $|m - n| = 2, n$ being even.
21.05.2023 15:53
Without loss of generality, let $m>n$ and let $m-n=k$. Therefore, the equation is $\text gcd(k,n) +\text gcd(k,n+1)+\text gcd(k,n+2)$. Claim: Maximum possible value of $\text gcd(k,n) +\text gcd(k,n+1)$ is $k+1$ Proof: Note that since $n$ and $n+1$ are relatively prime, the gcds above are also relatively prime. Since those two gcds have to be relatively prime factors of $k$, this means the maximum possible value is when $gcd(k,n) = k$ and $gcd(k,n+1) = 1$(the other case does not work as it does not let $\text gcd(k,n+2)$ to be $k$). Now since the maximum of $\text gcd(k,n+2)$ is $k$, the sum in problem is less than or equal to $2k+1$. Equality occurs when the optimal case shown above is satisfied. Because $gcd(k,n) = gcd(k,n+2) = k$, $k|2$, so $k$ is either 1 or 2. Quick computation gives us that m and n have to be consecutive integers or even consecutive integers.
29.06.2023 10:57
Lemma 1:- For $a,b \in \mathbb{Z}^{+}, a>b$ we have $\gcd(a,b)=\gcd(a,a-b)$ Pf:- denote $\gcd(a,b)=d$ , we have $d|a,d|b \implies d|a-b \implies d|\gcd(a,a-b)$ consider $\gcd(a,a-b)=d_{0}$ , we have $d_{0}|a, d_{0}|a-b \implies d_{0}|b \implies d_{0}|\gcd(a,b) \implies d_{0}|d \implies d=d_{0}$ $\square$ Lemma 2:- for $a,b \in \mathbb{Z}^{+}$ , $a>b$ we have $\gcd(a,b) \leqslant b$ Pf:- $\gcd(a,b)|b \implies b=\ell \cdot \gcd(a,b) , \ell \in \mathbb{Z}^{+}$ but if $\gcd(a,b)> b$ , we get a contradiction , hence the statement follows $\square$ Lemma 3:-if $\gcd(a,b)=d \neq 1$ , we have $1 \leqslant \gcd(a\pm 1 , b) \leqslant \frac{b}{2}$. Pf:- set $a=dx, b=dy$ where $\gcd(x,y)=1$ so we have $y=\frac{b}{d}$ and since $d>1$ we have $y \leqslant \frac{b}{2}$ also we have $a+1=dx+1$ and $b=dy$ so if $\gcd(a+1,b)=\mathcal{T}$ we have $\mathcal{T}|dx+1$ and $\mathcal{T}|dy \implies \mathcal{T}|y \implies \mathcal{T} \leqslant y \leqslant \frac{b}{2}$ so , we have $1 \leqslant \mathcal{T} \leqslant \frac{b}{2}$, similarly the case of $a-1$ follows similarly, $\square$ Now consider $z=\gcd(m+1,n+1)$. Case 1:- if $z=1$ then $\sum_{i=0}^{2} \gcd(m+i,n+i)=\gcd(m,|m-n|)+\gcd(m+1,|m-n|)+\gcd(m+2,|m-n|)$ (from Lemma 1) Using Lemma 2 we have $\gcd(m,|m-n|)+\gcd(m+1,|m-n|)+\gcd(m+2,|m-n|) \leqslant 1+2|m-n|$ Case 2:- if $z \neq 1$ we have from Lemma 3 we have $\sum_{i=0}^{2} \gcd(m+i,n+i)=\gcd(m,|m-n|)+\gcd(m+1,|m-n|)+\gcd(m+2,|m-n|) \leqslant |m-n|+\frac{|m-n|}{2}+\frac{|m-n|}{2} =2|m-n| < 2|m-n|+1$ so it concludes that $$\gcd(m,n) + \gcd(m+1,n+1) + \gcd(m+2,n+2) \le 2|m-n| + 1. $$ $\blacksquare$ Now the case of equality: since we can't have equality at case of $z \neq 1$ we must have $\gcd(m+1,|m-n|)=1$ and also we have $\gcd(m,|m-n|)=|m-n|, \gcd(m+2, |m-n|)=|m-n|$ which also means that $(|m-n|)|m , (|m-n|)|m+2 \implies (|m-n|)|2 \implies |m-n|=1,2$ so case of equality holds for $\boxed{\{ m \in \mathbb{Z}^{+}:(m,m-1),(m,m+1),(m,m-2),(m,m+2)\}}$ $\square$
18.12.2023 10:17
Finally my first non geo post in years Not as simple as The Dark Prince's sol but good enough Assume WLOG $m>n$ Notice that the expression is equivalent to $$gcd(m-n,n) + gcd(m-n,n+1) + gcd(m-n,n+2) \le 2|m-n| + 1. $$Now we know that $gcd(n+1,n)=gcd(n+1,n+2)=1$, which means they have no common factors, so let $$gcd(m-n,n+1)=p \implies gcd(m-n,n+1) \leq \frac{m-n}{p}$$and similarly $gcd(m-n,n+2) \leq \frac{m-n}{p}$ as $p$ does not divide $n,n+2$ but divides $m-n$. This means that $$gcd(m-n,n) + gcd(m-n,n+1) + gcd(m-n,n+2) \leq \frac{2(m-n)}{p}+p$$where $p | m-n$. It can be easily deduced that the max of this value occurs when $p=1$ which gives us the required inequality. The equality cases are when $m-n=1,2$ $\blacksquare$
24.01.2024 21:22
Assume $m>n$ and let $k=m-n$, by Euclid Algorithm it suffices to prove $$\gcd(m,k)+\gcd(m+1,k)+\gcd(m+2,k)\leq 2k+1$$It´s easy to note that $k=1$ always holds the equality and $k=2$ holds the equality when $m$ is even. Now, suppose $k>2$. Note that each $\gcd$ is a divisor of $k$ and since $m>k$ they are less than $k$, but at most one can be $k$ since they are consecutive, so the other two are at most $\frac{k}{2}$, this is $$\gcd(m,k)+\gcd(m+1,k)+\gcd(m+2,k)\leq k+\frac{k}{2}+\frac{k}{2}<2k+1$$
13.02.2024 06:02
WLOG let $m > n$ and let $a = m-n$. Then from the Euclidean Algorithm, we have $gcd(m,n) + gcd(m+1,n+1) + gcd(m+2,n+2) = gcd(a, n) + gcd(a, n+1) + gcd(a, n+2)$ $a \in \{1, 2\}$ is trivial ($a = 1$ is an equality case; $a = 2$ is an equality case if and only if $n$ is even). Otherwise, let $a > 2$. Clearly no two gcds are $a$; and since the largest proper divisor of $a$ is $\frac{a}{2}$, we have $$gcd(a, n) + gcd(a, n+1) + gcd(a, n+2) \le a + 2 \cdot \frac{a}{2} = 2a$$, so strict inequality holds but not equality. Therefore, the inequality is true with equality holding only in the cases mentioned above. $\square$
16.07.2024 19:25
WLOG let &m>n&, then let $l=m-n$. Then the inequality can be written as $gcd(m,l)+gcd(m+1,l)+gcd(m+2,l) \leq 2l+1$. Equality cases are $l=1,2.$ It is easy to see that at most one of the three $gcd$s can be equal to $l$, which is the maximum value. Since $\frac{l}{2}$ can be the largest divisor of $l$, other than itself. So, $gcd(m,l)+gcd(m+1,l)+gcd(m+2,l) \leq l+\frac{l}{2}+\frac{l}{2}=2l$.
22.10.2024 15:25
Notice that: $$S = \gcd(m, n)+\gcd(m+1, n+1)+\gcd(m+2, n+2) = \gcd(m-n, n)+\gcd(m-n, n+1)+\gcd(m-n, n+2).$$Note that: $\gcd(m-n, k) \le m-n$ for all integers $k$. Let's consider cases on $t=|m-n|$. Case-1: $t=1$: Then we have: $S=3 = 2t+1$. The given statement holds for this case. Case-2: $t=2$: Then we have: $S = \gcd(2, n)+\gcd(2, n+1)+\gcd(2, n+2) \le 2(2)+1 = 5$ where the equality holds when $n$ is even. Case-3: $t \ge 3$: Then we must have $t=|m-n|$ to occur at-most once amongst these numbers: $\gcd(m-n, n), \gcd(m-n, n+1), \gcd(m-n, n+2)$ (in-order to appear at-least twice we must have $t|2$ which doesnt satisfy $t \ge 3$). Thus, we have: $$\gcd(m-n, n)+\gcd(m-n, n+1)+\gcd(m-n, n+2) < t + 2 \cdot \tfrac{t}{2} < 2 t + 1 = 2|m-n|+1.$$In this case, the equality never holds. Hence the given statement is proved, where equality holds only when: - $|m-n|=1$ - $|m-n|=2$ and $n$ is even
21.01.2025 07:56
WLOG assume $n >m$. First note that, \[\gcd(m,n)+\gcd(m+1,n+1)+\gcd(m+2,n+2)=\gcd(m,n-m)+\gcd(m+1,n-m)+\gcd(m+2,n-m)\]The entire idea of the solution is the following claim. Claim : At most one of the values of $\gcd(m,n-m),\gcd(m+1,n-m)$ and $\gcd(m+1,n-m)$ can be $n-m$ for all $n,m$ such that $|n-m|>2$. Proof : If $\gcd(m,n-m)=m-n=\gcd(m+1,n-m)$, $n-m \mid m,m+1$ which implies that $n-m\mid 1$ so $n-m=1$. Similarly, it is impossible to have $\gcd(m+1,n-m)=m-n=\gcd(m+2,n-m)$. Further, if $\gcd(m,n-m)=m-n=\gcd(m+2,n-m)$ , $n-m \mid m,m+2$ which implies that $n-m \mid 2$ so $n-m \le 2$. This proves the claim. We now split into three cases. Case 1 : $n=m+1$. Then, \[\gcd(m,n-m)+\gcd(m+1,n-m)+\gcd(m+2,n-m) = \gcd(m,1)+\gcd(m+1,1)+\gcd(m+2,1)=3=2|m-n|+1\]Thus equality always holds in this case. Case 2 : $n=m+2$. Then, \[\gcd(m,n-m)+\gcd(m+1,n-m)+\gcd(m+2,n-m) = \gcd(m,2)+\gcd(m+1,2)+\gcd(m+2,2)\]Notice that each $\gcd$ is at most two and further, all three cannot be 2 (as one of $m$) and $m+1$ must be odd. Thus, \[\gcd(m,n-m)+\gcd(m+1,n-m)+\gcd(m+2,n-m) \le 5 = 2|m-n|+1\]with equality if and only if two of the $\gcd$ are 2 which requires $2\mid m$. Case 3 : $n>m+2$. Then, due to our claim, at most one of the terms is $n-m$. Since the other terms are also divisors of $n-m$ there are each at most $\frac{n-m}{2}$. Thus, \[\gcd(m,n-m)+\gcd(m+1,n-m)+\gcd(m+2,n-m) \le n-m + \frac{n-m}{2} + \frac{n-m}{2} = 2(n-m) < 2|m-n|+1\]so equality never holds in this case. This proves the inequality with equality holding only for the pairs $(m,n) = (k,k+1)$ and $(m,n)=(2k,2k+2)$ for all $k\ge 1$ (and permutations).