2014 dxdy logo

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

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




Начать новую тему Ответить на тему На страницу 1, 2  След.
 
 Необычное диофантово уравнение
Сообщение05.08.2024, 15:05 
Заслуженный участник


20/12/10
9042
Дан многочлен с целыми коэффициентами $f(x)=x^{2m}+x^{m+n}-4x^m+x^{m-n}+1$, где $m>n$ --- взаимно простые натуральные числа. Найдите $\gcd{(f(x),f'(x))}$.

Комментарий. Здесь я не берусь даже выписать это самое диофантово уравнение, но оно есть и его можно решить (неизвестные --- это $m$ и $n$). Задача была предложена на последней Сибирской математической олимпиаде в категории студентов-первокурсников, но никто из участников ее не решил.

 Профиль  
                  
 
 Re: Необычное диофантово уравнение
Сообщение09.08.2024, 10:48 
Заслуженный участник
Аватара пользователя


18/05/06
13438
с Территории
$x^{gcd(m,n)}-1$, что ли? Сложно.

 Профиль  
                  
 
 Re: Необычное диофантово уравнение
Сообщение09.08.2024, 12:23 
Заслуженный участник


20/12/10
9042
ИСН в сообщении #1648957 писал(а):
Сложно.
Что именно сложно? Если $m$ и $n$ не взаимно просты, то ответ, скорее всего, $x^{\gcd{(m,n)}}-1$, но над этим я не думал. Там другие обобщения интересны.

Как задача-то вообще, симпатичная?

 Профиль  
                  
 
 Re: Необычное диофантово уравнение
Сообщение15.08.2024, 21:45 
Заслуженный участник


20/12/10
9042
Случай, когда $m$ и $n$ не взаимно просты, очевидным образом сводится к случаю $\gcd{(m,n)}=1$, так что интереса не представляет.

 Профиль  
                  
 
 Re: Необычное диофантово уравнение
Сообщение15.08.2024, 23:42 
Аватара пользователя


07/01/16
1603
Аязьма
Интересно, тут общий множитель $x-1$ виден "на глазок", т.е. сложность и интерес задачи в том, чтобы доказать, что получившиеся после его отделения бегемоты взаимно просты?

 Профиль  
                  
 
 Re: Необычное диофантово уравнение
Сообщение16.08.2024, 00:35 
Заслуженный участник


20/12/10
9042
waxtep в сообщении #1650215 писал(а):
сложность и интерес задачи в том, чтобы доказать, что получившиеся после его отделения бегемоты взаимно просты?
Ну да. По-моему, это неочевидно. Исходный многочлен на самом деле малочлен, но после деления его на $x-1$ становится именно что бегемотом.

 Профиль  
                  
 
 Re: Необычное диофантово уравнение
Сообщение23.08.2024, 00:38 
Модератор
Аватара пользователя


11/01/06
5702
Имеем $f(x) = (x^m-1)^2 + x^{m-n}(x^n-1)^2$ и
$$g(x) := f'(x)/x^{m-n-1} = 2mx^n(x^m-1) + ((m+n)x^n - (m-n))(x^n-1).$$
Наша цель найти значение $h(x) := \gcd(f(x),g(x))$.

Переписываем $f(x)\equiv g(x)\equiv 0\pmod{h(x)}$ в виде системы сравнений:
$$\begin{cases}
(x^m-1)^2 \equiv - x^{m-n}(x^n-1)^2 \pmod{h(x)}\\
2mx^n(x^m-1) \equiv -((m+n)x^n - (m-n))(x^n-1)\pmod{h(x)}
\end{cases}$$
Возводя второе сравнение в квадрат и подставляя первое, имеем
$$-4m^2x^{m+n}(x^n-1)^2 \equiv ((m+n)x^n - (m-n))^2(x^n-1)^2 \pmod{h(x)}.$$
Ввиду $\gcd(m,n)=1$ и $g'(1) = 2m^2 + 2n^2$ имеем также $\gcd((x^n-1)^2,h(x))=x-1$. Поэтому сокращение $(x^n-1)^2$ в последнем сравнении даёт:
$$-4m^2x^{m+n} \equiv ((m+n)x^n - (m-n))^2 \pmod{h(x)/(x-1)},$$
что переписываем в виде:
$$-4m^2x^n(x^m-1) \equiv ((m+n)^2 x^n - (m-n)^2) (x^n-1) \pmod{h(x)/(x-1)}.$$
Подставляя второе сравнение системы и сокращая $x^n-1$, получаем:
$$2m((m+n)x^n - (m-n)) \equiv (m+n)^2 x^n - (m-n)^2 \pmod{h(x)/(x-1)},$$
т.е.
$$(m^2-n^2)(x^n - 1) \equiv 0  \pmod{h(x)/(x-1)}.$$
Поэтому $h(x)/(x-1)=1$, что дает $h(x)=x-1$.

-- Thu Aug 22, 2024 16:41:56 --

PS. Какой-то хитрый "алгоритм Евклида" получился. Хорошая задачка, но кажется ее можно как-то обобщить...

 Профиль  
                  
 
 Re: Необычное диофантово уравнение
Сообщение23.08.2024, 08:13 
Заслуженный участник


20/12/10
9042
Вот это да, еще один приятный сюрприз :-) На меня обрушился вал новых для меня идей! Буду разгребать постепенно, сразу все не осилить.

 Профиль  
                  
 
 Re: Необычное диофантово уравнение
Сообщение23.08.2024, 19:45 
Модератор
Аватара пользователя


11/01/06
5702
Всегда стараюсь избегать ручной работы, так как велика вероятность ошибки, и здесь она не заставила себя ждать:
maxal в сообщении #1651115 писал(а):
$$-4m^2x^{m+n} \equiv ((m+n)x^n - (m-n))^2 \pmod{h(x)/(x-1)},$$
что переписываем в виде:
$$-4m^2x^n(x^m-1) \equiv ((m+n)^2 x^n - (m-n)^2) (x^n-1) \pmod{h(x)/(x-1)}.$$

Правильно будет:
$$-4m^2x^n(x^m-1) \equiv ((m+n)^2 x^n + (m-n)^2) (x^n+1) \pmod{h(x)/(x-1)}.$$
Соответственно далее будет:
$$(m^2 - n^2)(x^n-1)^2 -4(m^2+n^2)x^n\equiv 0 \pmod{h(x)/(x-1)}$$
где сократить $x^n-1$ уже не получается. Надо думать дальше.

По большому счёту, чем я тут занимался - это исключение переменных. А для этого можно попросту сделать так: представить $x^nf(x)$ и $g(x)$ как многочлены от переменных $u:=x^m$ и $v:=x^n$ и вычислить их результант относительно $u$:
$$v \cdot (v - 1)^{2} \cdot \left((-m^{2} + n^{2}) v^{2} + (6 m^{2} + 2 n^{2}) v - m^{2} + n^{2}\right)$$
Откуда следует, что $h(x)/(x-1)$ делит $(m^{2} - n^{2}) x^{2n} - (6 m^{2} + 2 n^{2}) x^n + (m^{2} - n^{2})$, что совпадает с исправленным ручным результатом выше.

 Профиль  
                  
 
 Re: Необычное диофантово уравнение
Сообщение24.08.2024, 09:12 
Заслуженный участник


20/12/10
9042
maxal в сообщении #1651215 писал(а):
представить $x^nf(x)$ и $g(x)$ как многочлены от переменных $u:=x^m$ и $v:=x^n$
Вот ровно это я и делал. Далее можно просто решить систему уравнений относительно $u$ и $v$, там же только квадратные уравнения.

 Профиль  
                  
 
 Re: Необычное диофантово уравнение
Сообщение24.08.2024, 17:27 
Модератор
Аватара пользователя


11/01/06
5702
nnosipov в сообщении #1651241 писал(а):
Далее можно просто решить систему уравнений относительно $u$ и $v$, там же только квадратные уравнения.

Да, я тоже смотрел в эту сторону. Получается уравнение:
$$\big(\frac{3m^2+n^2}{m^2-n^2} \pm \frac{2m}{m^2-n^2}\sqrt{2(m^2+n^2)}\big)^m = \big(- \frac{m^2+3n^2}{m^2-n^2} \pm \frac{2n}{m^2-n^2}\sqrt{2(m^2+n^2)}\big)^n$$
Так как левая скобка положительна, а правая отрицательна, то $n$ четно, а $m$ соответственно нечётно. Тогда $2(m^2+n^2)\equiv 2\pmod{8}$ не является квадратом, то есть мы имеем дело с квадратичными иррациональностями. Но вот что дальше?

 Профиль  
                  
 
 Re: Необычное диофантово уравнение
Сообщение24.08.2024, 17:45 
Заслуженный участник


20/12/10
9042
maxal в сообщении #1651277 писал(а):
Но вот что дальше?
Да просто сравнить по величине левую и правую часть (напомню, у нас $m>n$).

 Профиль  
                  
 
 Re: Необычное диофантово уравнение
Сообщение24.08.2024, 17:51 
Модератор
Аватара пользователя


11/01/06
5702
Не получается для этого выбора знаков:
$$\big(\frac{3m^2+n^2}{m^2-n^2} - \frac{2m}{m^2-n^2}\sqrt{2(m^2+n^2)}\big)^m = \big(\frac{m^2+3n^2}{m^2-n^2} + \frac{2n}{m^2-n^2}\sqrt{2(m^2+n^2)}\big)^n$$
Или я чего-то не вижу?

 Профиль  
                  
 
 Re: Необычное диофантово уравнение
Сообщение24.08.2024, 18:59 
Заслуженный участник


20/12/10
9042
maxal в сообщении #1651280 писал(а):
Или я чего-то не вижу?
А там у системы только два решения (т.е. не все знаки допустимы). И для этих двух решений вроде бы все окей. Более точно, речь идет о системе $$u+1/u+v+1/v=4, \quad m(u-1/u)+n(v-1/v)=0,$$ где $u=x^m$, $v=x^n$. Она, помимо тривиального решения $(u,v)=(1,1)$, имеет еще ровно два решения $(u,v) \in \{(u_0,v_0),(u_0^{-1},v_0^{-1})\}$, где $$u_0=-\frac{m^2+3n^2+2n\sqrt{2(m^2+n^2)}}{m^2-n^2}, \quad
v_0=\frac{3m^2+n^2+2m\sqrt{2(m^2+n^2)}}{m^2-n^2}.$$Проверьте.

 Профиль  
                  
 
 Re: Необычное диофантово уравнение
Сообщение24.08.2024, 19:00 
Заслуженный участник
Аватара пользователя


26/02/14
551
so dna
maxal в сообщении #1651280 писал(а):
Не получается для этого выбора знаков:
$$\big(\frac{3m^2+n^2}{m^2-n^2} - \frac{2m}{m^2-n^2}\sqrt{2(m^2+n^2)}\big)^m = \big(\frac{m^2+3n^2}{m^2-n^2} + \frac{2n}{m^2-n^2}\sqrt{2(m^2+n^2)}\big)^n$$
Или я чего-то не вижу?


Левая часть меньше единицы, а правая больше:

$\left(\frac{3m^2+n^2}{m^2-n^2}-\frac{2m}{m^2-n^2}\sqrt{2\left(m^2+n^2\right)}\right)^m=\left(1 - \frac{4(m^2+n^2)}{2m\sqrt{2(n^2+m^2)}+2(n^2+m^2)}\right)^m<1$

$\left(\frac{m^2+3n^2}{m^2-n^2}+\frac{2n}{m^2-n^2}\sqrt{2(m^2+n^2)}\right)^n=\left(1 + \frac{2n\sqrt{2(n^2+m^2)}+4n^2}{m^2-n^2}\right)^n>1$

Или должно быть наоборот?

 Профиль  
                  
Показать сообщения за:  Поле сортировки  
Начать новую тему Ответить на тему  [ Сообщений: 21 ]  На страницу 1, 2  След.

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



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

Сейчас этот форум просматривают: mihiv, ИСН


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

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