М1812. Доказать тождество

Задача из журнала «Квант»(2002 год, 2 выпуск)

Условие

Натуральные числа $а$, $b$ и $с$ таковы, что НОД $(a^2-1, b^2-1, c^2-1) = 1$.

Докажите, что НОД$(ab+c, bc+a, ca+b) =$ НОД$(a, b, c) $(НОД – наибольший общий делитель.)

Рассмотрим произвольное простое число $р$ и докажем, что оно входит в НОД$(a^2-1, b^2-1, c^2-1)$ и НОД$(a, b, c)$ в равной степени. Заметим, что если НОД$(a, b, c)\vdots p$, то степень вхождения $р$ в оба НОДа равна наименьшей степени вхождения $р$ в числа $а, b, c$ (если НОД$(a, b, c)\vdots p^{k}$ , но $c$ не делится на $p^{k+1}$, то $ab+c$ делится на $p^{k}$, но не делится на $p^{k+1}$). Поэтому достаточно доказать, что любой простой делитель $q$ числа НОД$(ab+c, bc+a, ca+b)$ делит НОД$(a, b, c)$. Пусть, скажем, $а$ не делится на $q$, тогда, поскольку $bc + a$ не делится на $q$, получаем, что $b$ не делится на $q$ и $с$ не делится на $q$. Тогда $(ab+c)(bc+a)-a(ab+c)-c(bc+a) = ac(b^2-1)\vdots q$. Стало быть, $(b^2-1)\vdots q$. Аналогично, $(a^2-1)\vdots q$ и $(c^2-1)\vdots q$ – это уже противоречие с тем, что НОД$(a^2-1, b^2-1, c^2-1) = 1$. Значит, НОД$(ab+c, bc+a, ca+b) =$ НОД$(a, b, c)$.

А.Голованов