Необычное диофантово уравнение

[nnosipov]

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

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

[ИСН]

$x^{gcd(m,n)}-1$, что ли? Сложно.

[nnosipov]

ИСН в сообщении #1648957 писал(а):

Сложно.

Что именно сложно? Если $m$ и $n$ не взаимно просты, то ответ, скорее всего, $x^{\gcd{(m,n)}}-1$, но над этим я не думал. Там другие обобщения интересны.

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

[nnosipov]

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

[waxtep]

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

[nnosipov]

waxtep в сообщении #1650215 писал(а):

сложность и интерес задачи в том, чтобы доказать, что получившиеся после его отделения бегемоты взаимно просты?

Ну да. По-моему, это неочевидно. Исходный многочлен на самом деле малочлен, но после деления его на $x-1$ становится именно что бегемотом.

[maxal]

Имеем $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. Какой-то хитрый "алгоритм Евклида" получился. Хорошая задачка, но кажется ее можно как-то обобщить...

[nnosipov]

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

[maxal]

Всегда стараюсь избегать ручной работы, так как велика вероятность ошибки, и здесь она не заставила себя ждать:

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})$, что совпадает с исправленным ручным результатом выше.

[nnosipov]

maxal в сообщении #1651215 писал(а):

представить $x^nf(x)$ и $g(x)$ как многочлены от переменных $u:=x^m$ и $v:=x^n$

Вот ровно это я и делал. Далее можно просто решить систему уравнений относительно $u$ и $v$, там же только квадратные уравнения.

[maxal]

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}$ не является квадратом, то есть мы имеем дело с квадратичными иррациональностями. Но вот что дальше?

[nnosipov]

maxal в сообщении #1651277 писал(а):

Но вот что дальше?

Да просто сравнить по величине левую и правую часть (напомню, у нас $m>n$).

[maxal]

Не получается для этого выбора знаков:

$$\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$$

Или я чего-то не вижу?

[nnosipov]

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}.$$

Проверьте.

[Rak 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$

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