2014 dxdy logo

Научный форум dxdy

Математика, Физика, Computer Science, Machine Learning, LaTeX, Механика и Техника, Химия,
Биология и Медицина, Экономика и Финансовая Математика, Гуманитарные науки




Начать новую тему Ответить на тему
 
 Задача на делимость из Вишкиля
Сообщение10.07.2019, 15:51 
Заморожен
Аватара пользователя


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

 Профиль  
                  
 
 Re: Задача на делимость из Вишкиля
Сообщение10.07.2019, 18:32 
Заслуженный участник


20/12/10
8858
Вообще, задача простая, но немножко неприятная. Пусть сначала $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$ и цель достигнута.

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

 Профиль  
                  
 
 Re: Задача на делимость из Вишкиля
Сообщение11.07.2019, 10:36 
Заморожен
Аватара пользователя


31/10/11
123
Челябинск
Я решал задачу похожим образом.
Пусть $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$.
Наверное, есть более простое рассуждение!

 Профиль  
                  
 
 Re: Задача на делимость из Вишкиля
Сообщение11.07.2019, 12:25 
Заслуженный участник


20/12/10
8858
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$.

 Профиль  
                  
 
 Re: Задача на делимость из Вишкиля
Сообщение11.07.2019, 14:00 
Заморожен
Аватара пользователя


31/10/11
123
Челябинск
Да, Ваше решение проще!
Спасибо!

 Профиль  
                  
 
 Re: Задача на делимость из Вишкиля
Сообщение11.07.2019, 16:18 
Модератор
Аватара пользователя


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

 Профиль  
                  
 
 Re: Задача на делимость из Вишкиля
Сообщение11.07.2019, 18:13 
Заслуженный участник


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

 Профиль  
                  
Показать сообщения за:  Поле сортировки  
Начать новую тему Ответить на тему  [ Сообщений: 7 ] 

Модераторы: Модераторы Математики, Супермодераторы



Кто сейчас на конференции

Сейчас этот форум просматривают: нет зарегистрированных пользователей


Вы не можете начинать темы
Вы не можете отвечать на сообщения
Вы не можете редактировать свои сообщения
Вы не можете удалять свои сообщения
Вы не можете добавлять вложения

Найти:
Powered by phpBB © 2000, 2002, 2005, 2007 phpBB Group