Natural $a,b,c$ are $>100$ and $(a,b,c)=1$. $c|a+b,a|b+c$ Find minimal $b$
Problem
Source: St Petersburg Olympiad 2012, Grade 9, P2
Tags: number theory
02.10.2017 08:34
$a\ne b\ne c\ne a$ Assume $a=b$. From $a|b+c \Longrightarrow a|a+c\Longrightarrow a|c \Longrightarrow gcd(a,b,c)=a>100>1$, contradiction. Hence, $a\ne b$. Similarly, $a\ne c, b\ne c$. $\max{(a,b,c)}=b$. WLOG, let $a<c$. Assume $c>b$. Results $a+b<2c$. $c|a+b \Longrightarrow a+b=kc, k\in\mathbb{N}^* \Longrightarrow kc<2c\Longrightarrow k<2 \Longrightarrow k=1 \Longrightarrow c=a+b$. $a|b+c \Longrightarrow a|a+2b \Longrightarrow a|2b$. For $a$ odd number, results $a|b$. For $a$ even number, $a=2a_1, a_1\in\mathbb{N} \Longrightarrow \dfrac{a}{2}=a_1|b$. Results $gcd(a,b,c)=gcd(a,b,a+b)\ge \dfrac{a}{2}>50>1$, contradiction. Hence $b>c>a$. $gcd(a,c)=1$. Assume $gcd(a,c)=d>1$. $a|b+c \Longrightarrow d|b+c \Longrightarrow d|b \Longrightarrow gcd(a,b,c)\ge d>1$, contradiction. Results $gcd(a,c)=1 \Longrightarrow \exists m,n\in\mathbb{Z}$ such that $ma+nc=1\quad(1)$. $a|b+c \Longrightarrow a|a+b+c \Longrightarrow ac|c(a+b+c)\quad(2)$. $c|a+b \Longrightarrow c|a+b+c \Longrightarrow ac|a(a+b+c)\quad(3)$. From $(1),(2)$ and $(3)$ results $ac|ma(a+b+c)+nc(a+b+c) \Longrightarrow ac|a+b+c \Longrightarrow a+b+c=pac, p\in\mathbb{N}^*$. The minimum value of $b$ is obtained for $ac=a+b+c$. Results: $b=ac-a-c=(a-1)(c-1)-1$. $a\ge 101, c\ge 102$. $\min{(b)}=\min{(a-1)}\cdot\min{(c-1)}-1=100\cdot101-1=10099$. The minimum value of $b$ is $10099$.
02.10.2017 09:00
WallyWalrus wrote: $a\ne b\ne c\ne a$ Assume $a=b$. From $a|b+c \Longrightarrow a|a+c\Longrightarrow a|c \Longrightarrow gcd(a,b,c)=a>100>1$, contradiction. Hence, $a\ne b$. Similarly, $a\ne c, b\ne c$. $\max{(a,b,c)}=b$. WLOG, let $a<c$. Assume $c>b$. Results $a+b<2c$. $c|a+b \Longrightarrow a+b=kc, k\in\mathbb{N}^* \Longrightarrow kc<2c\Longrightarrow k<2 \Longrightarrow k=1 \Longrightarrow c=a+b$. $a|b+c \Longrightarrow a|a+2b \Longrightarrow a|2b$. For $a$ odd number, results $a|b$. For $a$ even number, $a=2a_1, a_1\in\mathbb{N} \Longrightarrow \dfrac{a}{2}=a_1|b$. Results $gcd(a,b,c)=gcd(a,b,a+b)\ge \dfrac{a}{2}>50>1$, contradiction. Hence $b>c>a$. $gcd(a,c)=1$. Assume $gcd(a,c)=d>1$. $a|b+c \Longrightarrow d|b+c \Longrightarrow d|b \Longrightarrow gcd(a,b,c)\ge d>1$, contradiction. Results $gcd(a,c)=1 \Longrightarrow \exists m,n\in\mathbb{Z}$ such that $ma+nc=1\quad(1)$. $a|b+c \Longrightarrow a|a+b+c \Longrightarrow ac|c(a+b+c)\quad(2)$. $c|a+b \Longrightarrow c|a+b+c \Longrightarrow ac|a(a+b+c)\quad(3)$. From $(1),(2)$ and $(3)$ results $ac|ma(a+b+c)+nc(a+b+c) \Longrightarrow ac|a+b+c \Longrightarrow a+b+c=pac, p\in\mathbb{N}^*$. The minimum value of $b$ is obtained for $ac=a+b+c$. Results: $b=ac-a-c=(a-1)(c-1)-1$. $a\ge 101, c\ge 102$. $\min{(b)}=\min{(a-1)}\cdot\min{(c-1)}-1=100\cdot101-1=10099$. The minimum value of $b$ is $10099$. How are you so good at math???!!!
03.10.2017 08:34
let $c=a+k$ for some $k \in \mathbb{N}$. then from $c|a+b$ we get $b=na+(n+1)k$. from $a|c+b$ we get that $a|(n+2)k$. now from $(a,b,c)=1$ we get that $(a,k)=1$ as well (so we can just set $k$ to 1 to minimize $b$) so $a|n+2$. so $n \geq 99$ and $b_{min} \geq 99(101)+100(1) = 10099$ we see that $(a,b,c)=(101,102,10099)$ works so $b_{min}=10099$