Determining the maximum GCD

Without loss of generality, we can assume that $a < b< c$ . If $n$ is the greatest common divisor of $ab+1,ac+1,bc+1$ , then since $n$ divides $ab+1$ it follows that $n$ and $a$ are coprime. Similarly $n$ and $b$ are coprime and $n$ and $c$ are coprime. Also note that $n$ divides $a(b-c) = (ab+1)-(ac+1)$ , and so $n$ divides $b-c$ . Similarly we can show that $n$ divides $a-b$ . Thus we must have $b = a+un$ , $c = a+vn$ where $u,v$ are positive integers with $u < v$ . Since $n$ divides $ab+1$ we deduce that $n$ divides $a^2+1$ .

Since $n$ divides $a^2+1$ we deduce that $\sqrt{n-1} \le a$ . Since $b \ge a+n$ and $c \ge a+2n$ we deduce that $3000000 \ge a+b+c \ge 3(a+n)$ , so that $a \le 1000000 - n$ . Thus $n$ must be such that $\sqrt{n-1} \le 1000000 - n$ , and hence $n \le \tfrac12 \big(2000001 - \sqrt{3999997}\big) = 999000.5004$ , so that $n \le 999000$ . We note that $n \; = \; 999^2 + 1 = 998002 \hspace{1cm} a \; = \; 999 \hspace{1cm} b = a + n = 999001 \hspace{1cm} c = a + 2n = 1997003$ is a particular solution, and hence $998002 \le n \le 999000$ .

At this point we only need conduct a computer search to find the largest value of $n$ giving a solution to the problem (there are fewer than $1000$ cases to check): $n \; = \; \boxed{998285} \hspace{1cm} a \; = \; 1413 \hspace{1cm} b = a + n = 999698 \hspace{1cm} c = a + 2n = 1997983$

We can assume that $a>b>c$ , let $b-c=x,a-b=y$ . We have $3c+2x+y\leq 3000000$ .

Let $d=\text{gcd} (ab+1,bc+1,ca+1)$ , we get $\text{gcd} (d,a)=\text{gcd} (d,b)=\text{gcd} (d,c)=1$ .

So $d\mid a-c,a-b\Rightarrow d\mid \text{gcd} (x,y)$ .

Also, $d\mid c^2+1$ . We get $d\leq c^2+1,x,y\Rightarrow 3000000\geq 3c+3d\geq 3\sqrt{d-1} +3d$ .

This gives us $d\leq 999001$ .

If $d=c^2+1$ , we have $d\leq 999^2+1=998002$ .

If $d= \frac{c^2+1}{2}$ , we get $3000000\geq 3\sqrt{2d-1}+3d$ . This gives us $d\leq 998587$ , so $d\leq \frac{1413^2+1}{2}=998285$ .

If $d\leq \frac{c^2+1}{5}$ , we get $3000000\geq 3\sqrt{5d-1}+3d$ . This gives us $d\leq 997766$ .

So, the maximum value of $d$ is $998285$ . Equality holds at $c=1413,x=y=998285$ .