Задача на делимость из Вишкиля

[Alexander Evnin]

Увидел в материалах Кировской ЛМШ 2018 г. такую задачу.
Пусть $a, b, c, d$ --- натуральные числа, $ac+bd$ делится на $a^2+b^2$.
Докажите, что числа $a^2+b^2$ и $c^2+d^2$ не являются взаимно простыми.
Доказательство я нашёл, но надеюсь, что имеется более короткое!

[nnosipov]

Вообще, задача простая, но немножко неприятная. Пусть сначала $a$ и $b$ --- взаимно простые числа. Возьмем произвольный простой делитель $p$ числа $a^2+b^2$. Имеем

$$a^2+b^2 \equiv 0 \pmod{p}, \quad ac+bd \equiv 0 \pmod{p},$$

откуда выводим $a^2(c^2+d^2) \equiv 0 \pmod{p}$. Но $a$ не делится на $p$ (иначе и $b$ делилось бы на $p$, что невозможно из-за взаимной простоты $a$ и $b$). Значит, $c^2+d^2$ делится на $p$ и цель достигнута.

Далее осталось понять, как общий случай сводится к уже разобранному. Фактически это почти очевидно, но почему-то до меня дошло не сразу.

[Alexander Evnin]

Я решал задачу похожим образом.
Пусть $p$ - простой делитель числа $a^2+b^2$. Тогда, как показано выше, $a^2(c^2+d^2)$ делится на $p$.
Аналогично устанавливается, что $b^2(c^2+d^2)$ делится на $p$.
Если $c^2+d^2$ кратно $p$, то всё доказано.
Иначе $a$ и $b$ делятся на $p$. Пусть $a=pa_1$, $b=pb_1$. После несложных преобразований
придём к тому, что $a_1c+b_1d$ делится на $a_1^2+b_1^2$. Перешли к аналогичной задаче с заменой пары $(a,b)$ парой $(a_1,b_1)$, где $a^2+b^2$ делится на $a_1^2+b_1^2$.
Повторяя эту операцию, в конце концов придём к паре взаимно простых чисел $(a_n,b_n)$,
для которых числа $a_n^2(c^2+d^2)$ и $b_n^2(c^2+d^2)$ кратны некоторому простому делителю $q$ числа $a_n^2+b_n^2$. Тогда $a^2+b^2$ и $c^2+d^2$ делятся на $q$.
Наверное, есть более простое рассуждение!

[nnosipov]

Alexander Evnin в сообщении #1404489 писал(а):

Повторяя эту операцию, в конце концов придём к паре взаимно простых чисел $(a_n,b_n)$

Эта идея понятна, но я имел в виду другое (на мой взгляд, более прозрачное) рассуждение. Пусть $t=\gcd{(a,b)}$ и $a=ta_1$, $b=tb_1$. По условию $ta_1c+tb_1d$ делится на $t^2a_1^2+t^2b_1^2$, что равносильно делимости $a_1c+b_1d$ делится на $ta_1^2+tb_1^2$. Как следствие, $a_1c+b_1d$ делится на $a_1^2+b_1^2$. Поскольку $\gcd{(a_1,b_1)}=1$, по доказанному $\gcd{(a_1^2+b_1^2,c^2+d^2)}>1$. Но тогда $\gcd{(a^2+b^2,c^2+d^2)}=\gcd{(t^2(a_1^2+b_1^2),c^2+d^2)}>1$.

[Alexander Evnin]

Да, Ваше решение проще!
Спасибо!

[maxal]

А все потому, что $\mathrm{Res}_a(ac+bd,a^2+b^2)=b^2(c^2+d^2)$.

[nnosipov]

Да, результант --- удобная конструкция для того, чтобы механически получать следствие данных соотношений (особенно в нелинейном случае).