Let $n$ be a positive integer. Determine the maximum value of $gcd(a, b) + gcd(b, c) + gcd(c, a)$ for positive integers $a, b, c$ such that $a + b + c = 5n$.
Problem
Source: Dutch IMO TST1 2019 p3
Tags: maximum, GCD, greatest common divisor, number theory
kaede
14.01.2020 01:23
Set $ f=f( a,b,c) =\gcd( a,b) +\gcd( b,c) +\gcd( c,a)$.
We wiil prove the following result :
The maximum value is $ \begin{cases}
f( 2n,n,n) =4n & \ \text{when} \ 3\nmid n\\
f( 5n/3,5n/3,5n/3) =5n & \ \text{when} \ 3\mid n
\end{cases}$.
proof
Let $ f$ be the maximum value for some $ ( a,b,c)$.
Since $ f\leq a+b+c=5n$, the maximum value is clearly $ 5n$ when $ 3\mid n$.
So we assume that $ n$ is not divisible by $ 3$.
Let $ ( a,b,c) =( ds,dt,du)$ where $ \gcd( s,t,u) =1$.
We have $ 5n=d( s+t+u)$ and $ f=d(\gcd( s,t) +\gcd( t,u) +\gcd( u,s))$.
If $ \gcd( s,t) \leq t/2, \gcd( t,u) \leq u/2, $ and $ \gcd( u,s) \leq s/2$,
then we have $ f\leq d( s+t+u) /2=5n/2$, but this is impossible.
So WLOG, we have $ \gcd( s,t) =t$, implying $ s=tk$ for some $ k$.
Let $ g=\gcd( u,k) .$
Since $ \gcd( tk,t,u) =1$, we have $ \gcd( t,u) =1$.
Furthermore, $ \gcd( u,s) =\gcd( u,tk) =\gcd( u,k) =g$.
We have $ f=d( t+1+g) =5n( t+g+1) /( tk+t+u)$.
Since $ f\geq 4n,$ we have $ $$ ( t+g+1) /( tk+t+u) \geq 4/5$.
It follows that $ ( 4k-1) t+4u\leq 5g+5$, implying $ t=1$.
So we have $ 5g+6\geq 4k+4u$.
If $ g\leq u/2$, then $ 5u/2+6\geq 4k+4u\ \Rightarrow \ 6\geq 4k+3u/2\geq 7$.
So we can say that $ g=u=k$.
It follows that $ 5k+6\geq 4k+4k=8k$, implying $ k\leq 2$.
If $ k=1$, then $ 5n=3d$, but this is impossible.
If $ k=2$, then $ f=4n$.
$ \blacksquare $
Ya_pank
27.04.2021 17:00
kaede wrote: The maximum value is $ \begin{cases} f( 2n,n,n) =4n & \ \text{when} \ 3\nmid n\\ f( 5n/3,5n/3,5n/3) =5n & \ \text{when} \ 3\mid n \end{cases}$. I don't think that's true. $f(1,1,5n-2)=10n-3>5n$
GorgonMathDota
27.04.2021 17:03
Ya_pank wrote: kaede wrote: The maximum value is $ \begin{cases} f( 2n,n,n) =4n & \ \text{when} \ 3\nmid n\\ f( 5n/3,5n/3,5n/3) =5n & \ \text{when} \ 3\mid n \end{cases}$. I don't think that's true. $f(1,1,5n-2)=10n-3>5n$ Dude $f(1,1,5n - 2) = \gcd(1,1) + \gcd(1,5n - 2) + \gcd(1,5n - 2) = 3 < 5n$.
Ya_pank
02.05.2021 17:22
yeah that was so dumb
raghoodah1m
16.11.2021 11:31
kaede wrote:
Set $ f=f( a,b,c) =\gcd( a,b) +\gcd( b,c) +\gcd( c,a)$.
We wiil prove the following result :
The maximum value is $ \begin{cases}
f( 2n,n,n) =4n & \ \text{when} \ 3\nmid n\\
f( 5n/3,5n/3,5n/3) =5n & \ \text{when} \ 3\mid n
\end{cases}$.
proof
Let $ f$ be the maximum value for some $ ( a,b,c)$.
Since $ f\leq a+b+c=5n$, the maximum value is clearly $ 5n$ when $ 3\mid n$.
So we assume that $ n$ is not divisible by $ 3$.
Let $ ( a,b,c) =( ds,dt,du)$ where $ \gcd( s,t,u) =1$.
We have $ 5n=d( s+t+u)$ and $ f=d(\gcd( s,t) +\gcd( t,u) +\gcd( u,s))$.
If $ \gcd( s,t) \leq t/2, \gcd( t,u) \leq u/2, $ and $ \gcd( u,s) \leq s/2$,
then we have $ f\leq d( s+t+u) /2=5n/2$, but this is impossible.
So WLOG, we have $ \gcd( s,t) =t$, implying $ s=tk$ for some $ k$.
Let $ g=\gcd( u,k) .$
Since $ \gcd( tk,t,u) =1$, we have $ \gcd( t,u) =1$.
Furthermore, $ \gcd( u,s) =\gcd( u,tk) =\gcd( u,k) =g$.
We have $ f=d( t+1+g) =5n( t+g+1) /( tk+t+u)$.
Since $ f\geq 4n,$ we have $ $$ ( t+g+1) /( tk+t+u) \geq 4/5$.
It follows that $ ( 4k-1) t+4u\leq 5g+5$, implying $ t=1$.
So we have $ 5g+6\geq 4k+4u$.
If $ g\leq u/2$, then $ 5u/2+6\geq 4k+4u\ \Rightarrow \ 6\geq 4k+3u/2\geq 7$.
So we can say that $ g=u=k$.
It follows that $ 5k+6\geq 4k+4k=8k$, implying $ k\leq 2$.
If $ k=1$, then $ 5n=3d$, but this is impossible.
If $ k=2$, then $ f=4n$.
$ \blacksquare $
"then we have $ f\leq d( s+t+u) /2=5n/2$, but this is impossible." sorry but I didn't get why is it impossible
Olympiader
16.11.2021 13:37
Write G = gcd(a, b) + gcd(b, c) + gcd(c, a). Without loss of generality we assume that a <b< c. Then we have gcd(a, b) < a, gcd(b, c) < b, and gcd(c, a) < a. Hence G=<a+b+a=< a +b+c=< 5n. If 3 | n, then we can achieve G = 5n via a = b = c =5/3 n. Since all three gcd's equal n, So suppose that 3does not divide n. Then a, b, and c cannot all be equal to each other. We distinguish a number of cases. . Case la. b = c and b =< 2n. Since in this case we have a≠b, it follows that gcd(a, b) = gcd(a, b-a) =<b-a. Hence G =< (b- a)+b+a = 2b =< 4n. Case 1b. b = c and b > 2n. We have a+2b = 5n, so a = 5n – 2b, from which we deduce that G =< a+b+a = 10n – 4b+b = 10n – 3b =< 10n – 6n = 4n. Case 2a. b≠c and c-a >= n. Now we have G =< a+b+a = (a+b+c)-(c-a)=5n – (c - a) < 5n – n = 4n. Case 2b. b≠c and c - a < n. Since a =<b=<c we now also have c- b < n. Moreover, we have b+c and therefore a + c. So gcd(c, a) = gcd(c- a, a) =<c-a < n and gcd(b, c) = gcd(b, c – b) =<c-b< n. Also note that a <n. Therefore G =<5/3n+n+n< 4n. So in all cases we have G< 4n. We can achieve G = 4n via a = n and b= c= 2n, since then we have gcd(a, b) = gcd(c, a) = n and gcd(b, c) = 2n. Therefore the maximum value of G is 5n if 3 divide n and 4n if 3 doesn't divide n.