Теория Чисел + неравенства

Во-первых посмотрим на 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.

Примечание: странно, но у меня получилось, что неравенство строгое.

6 симпатий

Можете объяснить, почему после второго шага в алгоритме Евклида, последовало (a-c, ab+1)?

Так как (b, ab+1)=1, b не влияет на НОД, и мы можем его сократить

2 симпатии