Во-первых посмотрим на d = (ab+1, bc+1, ca+1).
Заметим, что d | (ab+1, bc+1) = (b(a-c), ab+1) = (a-c, ab+1), а поэтому d делит |c-a|. Аналогично d делит |b-c| и |a-b|.
Из делимости и различности a,b,c понимаем, что d \leq min \{|c-a|, |b-c|, |a-b| \}. Но тогда докажем, что min \{|c-a|, |b-c|, |a-b| \} \leq \frac{a+b+c}{3}.
Без ограничения общности, a>b>c, тогда a-c = max \{|c-a|, |b-c|, |a-b| \}.
Если b-c \leq a-b, то 2b \leq a+c, а
b-c \leq \frac{a+b+c}{3} \Leftrightarrow 0 \leq a-2b+4c,
что верно, так как
a-2b+4c = (a+c - 2b) +3c \geq 3c>0.
Если же a-b \leq b-c, то a+c \leq 2b, и
a-b \leq \frac{a+b+c}{3} \Leftrightarrow 0 \leq 4b-2a+c,
что тоже верно, поскольку
4b-2a+c =(4b - 2(a+c))+3c \geq 3c > 0.
Примечание: странно, но у меня получилось, что неравенство строгое.
7 лайков
Можете объяснить, почему после второго шага в алгоритме Евклида, последовало (a-c, ab+1)?
Так как (b, ab+1)=1, b не влияет на НОД, и мы можем его сократить
3 лайка