Полиномы, сохраняющие взаимную простоту

[Руст]

Найти все полиномы $P(x)$ из $\mathbb{Q}[x]$, удовлетворяющие условиям:
1. $P(x)$ принимает целые значения при целых значениях аргумента,
2. Существует достаточно большое число $N$, что если $m>N,n>N и (m,n)=1$ (т.е. взаимно просты), то значения $P(m)$ и $P(n)$ так же взаимно просты.

[sceptic]

Наверное, им задача неинтересна . Посему предложу свое решение.

Для начала ослабим условие задачи, заменив $\mathbb{Q$$[x]}$ на $\mathbb{Z$$[x]}$. Тем самым мы упростим рассуждения, да и основная конструкция доказательства станет более воспринимаемой. Возврат к исходным условиям произведем чуть позже (писанина с тегами с непривычки отнимает у меня много времени) - там все рассуждение подвергнется небольшой модификации.

Докажем, что кроме полиномов $P(x)\equiv$ $\pm x^k, k=0,1,2,...$, других полиномов с условиями 1, 2 не существует.
Опущу банальный случай $P(x)\equiv$ $const$ - здесь все очевидно: решения - $P(x)\equiv$ $\pm 1$.
Пусть $P(x)\equiv$ $a_0x^k+a_1x^{k-1}+...+a_k_-_1x+a_k, k>0 $___________(*)
- полином, удовлетворяющий условиям 1, 2.

Далее нам понадобится простенькая
Лемма Если $m\in\mathbb{Z}, P(m)=A\ne0$, то $P(m)|P(m+A)$.
Доказательство леммы тривиально: подставляем $m+A$ в представление (*), раскрываем все биномы, отделяем все слагаемые, делящиеся на $A$ и видим, что оставшиеся слагаемые дают в сумме $P(m)$.

Приступим к основной задаче.
Из условия 1 вытекает, что $a_k = P(0)\in\mathbb{Z}$. Запомним это.
Пусть $a_k\ne0$.
Пусть $\exist N>0$, обеспечивает выполнение условия 2. В силу конечности числа корней у полиномов и бесконечности множества простых чисел существует простое число $p>N$, для которого $A\equiv$ $P(p)\ne0$, $|A|>1$ и $(p,a_k)=1$. Отсюда следует, что $(p,A)=1$ и, следовательно, $(p+A,p)=1$. Но, согласно лемме, $P(p)|P(p+A)$. Т.е. для пары $p,q=p+A$ имеем $(p,q)=1$ и $(P(p),P(q))=(A,P(p+A))=A$, что означает (ввиду $|A|>1$), что $P(p)$ и $P(q)$ не взаимно-просты. Мы пришли к противоречию с п. 2. Таким образом, мы доказали, что среди полиномов с $k>0$ и $a_k\ne0$ искомых полиномов не существует.
Пурист бы указал здесь на пробел в рассуждении: не рассмотрен случай, когда $A<0$ (тогда не выполняется требование $q>N$). Но, полагаю, пурист в состоянии сам в этом случае вместо полинома $P(x)$ расмотреть полином $-P(x)$.
Пусть теперь $a_k=0$.
Тогда либо $P(x)\equiv$ $a_0x^k$, либо для некоторого $l: k>l>0$ имеем $P(x)\equiv$ $x^{k-l}Q(x)$, где у полинома $Q(x)\equiv$ $b_0x^l+b_1x^{l-1}+...+b_{l-1}x+b_l $ свободный член $b_l$ отличен от нуля.
В первом случае легко убедиться, что полином удовлетворяет условию п.2 лишь при $a_0=\pm 1$, что мы и отражаем в ответе.
Во втором случае опять возьмем простое $p>N$, для которого $A\equiv$ $Q(p)\ne0$, $|A|>1$ и $(p,b_l)=1$. Наличие таких чисел обосновывается точно также, как и выше. Из выбора $p$ вытекает, что $(p,A)=1$ и, следовательно, $(p+A,p)=1$.
Вычислим теперь $P(p+A)$: $P(p+A)=(p+A)^{k-l}Q(p+A)=(p^{k-l}+AK)(Q(p)+AL)=$ $p^{k-l}Q(p)+A(KQ(p)+Lp^{k-l}+AKL) $ (буквами $K$ и $L$ обозначены суммы членов, образующихся при раскрытии биномов - как и при доказательстве леммы - в $(p+A)^{k-l}$ и $Q(p+A)$ соответственно). Теперь сразу видно, что $A|P(p+A)$, т.е. $A|(P(p),P(p+A))$ (помня, что $P(p)=p^{k-l}Q(p)=p^{k-l}A $). Вот мы и пришли к противоречию с п.2. Доказательство завершено.
Осталось вернуться к исходной .
Излагать решение для исходной, редакции задачи ($P\in\mathbb{Q$$[x]}$ ), по-видимому нет смысла, поскольку Руст итак его знает, а остальные заинтересованные читатели (коих не наблюдается) в состоянии самостоятельно, полагаю, воспроизвести его .

[Руст]

Очень обстоятельное доказательство. Можно было несколько проще и сразу для многочлена принимающего целые значения при целых значениях аргумента (отсюда следует, что коэффициенты рациональны).

[sceptic]

Руст писал(а):

Очень обстоятельное доказательство. Можно было несколько проще и сразу для многочлена принимающего целые значения при целых значениях аргумента (отсюда следует, что коэффициенты рациональны).

Писал импровизируя (отсюда и усложненность изложения), но так, чтобы и студентам было понятно. Насколько я понял, задачка имеет учебный характер.
Есть необходимость дать решение для $\mathbb{Q$$[x]}$? Приведенное выше рассуждение в этом случае "в лоб" не проходит - нужно его модифицировать.

[Руст]

Я то знаю решение. Можно вообще избавиться от первого условия. Для этого надо определит взаимную простоту чисел так, чтобы она годилось и на множестве рациональных чисел. Одним из таких определений является: $r_1$ и $r_2$ называется взаимно простыми, если $\mathbb{Z}$ модуль, порождённый этими элементами содержит $1$. Можно ослабить и второе условие. Для достаточно больших простых $p$ и $q$ рациональные значения $P(p)$ и $P(q)$ взаимно просты.

[sceptic]

Руст писал(а):

Я то знаю решение. Можно вообще избавиться от первого условия. Для этого надо определит взаимную простоту чисел так, чтобы она годилось и на множестве рациональных чисел. Одним из таких определений является: r1 и r2 называется взаимно простыми, если Z модуль, порождённый этими элементами содержит 1. Можно ослабить и второе условие. Для достаточно больших простых p и q рациональные значения P(p) и P(q) взаимно просты.

Я об этом догадался . Заключение в своем решении подправил.

[Руст]

Укажу свой путь решения. Пусть $p$ достаточно большое простое число и пусть числитель $P(p)$ делится на простое число $q$, отличное от $p$. Рассмотрим $x=p+kq^r$. Взяв $r$ достаточно большим добиваемся, чтобы числитель $f(x)$ делился так же на $q$, при этом $k$ можно подобрать так, чтобы $x$ был простым. Получаем два больших простых значения $p$ и $x$, что $P(p)$ и $P(x)$ не взаимно просты, следовательно, числитель $P(p)$ всегда является степенью простого числа $p$ для достаточно больших $p$. Так как знаменатели ограничены, то при достаточно больших $p$ числитель $P(p)$ может быть только $p^m$, где $m$ степень многочлена. Учитывая, что знаменатели имеют только конечное число возможностей (делитель НОК всех знаменателей коэффициентов) то одно из них реализуется для бесконечного количества значений. Используя, то что по $m+1$ значениям полином определяется однозначно получаем $P(x)=x^m/a$, $a$ - натуральное. При таком обобщении $a$ не определяется, т.е. некоторая целочисленность нужна. Например, что функция принимает целочисленное значение по крайней мере для двух простых значений аргумента.

[sceptic]

Руст писал(а):

Укажу свой путь решения. Пусть $p$ достаточно большое простое число и пусть числитель $P(p)$ делится на простое число $q$, отличное от $p$. Рассмотрим $x=p+kq^r$. Взяв $r$ достаточно большим добиваемся, чтобы числитель $f(x)$ делился так же на $q$, при этом $k$ можно подобрать так, чтобы $x$ был простым.

$f(x)$ - это $P(x)$?

Руст писал(а):

Получаем два больших простых значения $p$ и $x$, что $P(p)$ и $P(x)$ не взаимно просты, следовательно, числитель $P(p)$ всегда является степенью простого числа p для достаточно больших $p$. Так как знаменатели ограничены, то при достаточно больших $p$ числитель $P(p)$ может быть только $p^m$, где $m$ степень многочлена.

Последнее утверждение, пожалуйста, поподробнее. Для меня это не очевидно :) .

Руст писал(а):

Учитывая, что знаменатели имеют только конечное число возможностей (делитель НОК всех знаменателей коэффициентов) то одно из них реализуется для бесконечного количества значений. Используя, то что по $m+1$ значениям полином определяется однозначно получаем $P(x)=x^m/a$, $a$ - натуральное. При таком обобщении $a$ не определяется, т.е. некоторая целочисленность нужна. Например, что функция принимает целочисленное значение по крайней мере для двух простых значений аргумента.

[Руст]

1) Да вместо $f(x)$ надо $P(x)$.
2) Пусть $A=$НОК всех знаменателей коэффициентов. Тогда $АP(x)$ целочисленный многочлен. Мы доказали,что для достаточно больших простых чисел $P(p)=p^b(p)/a(p)$, $a(p)$ один из делителей $A$. Тогда найдется один из делителей $A$, для которых $a=a(p)$ для бесконечно большого количества простых чисел. Покажем, что из них найдётся бесконечное множество, для которых $b(p)=m$ - степени многочлена. Многочлен $P(x)$ при больших $x$ имеет вид $сx^m(1+o(1))$, $c$ - коэффициент, т.е $P(x)/x^m$ стремится к константе, что бы противоречило, если бы было бесконечно много исключений $b(p)$ отличных от $m$.
3) Самое слабое условие целочисленности. Существует два взаимно простых рациональных чисел $r_1$ и $r_2$, что $P(r_1),P(r_2)$ целые.

[sceptic]

Давайте следующую задачу(связанную с теорией чисел и, желательно, нетривиальную). Потренируем мозги .

[Руст]

Нетривиальная задача.
Натуральные числа от $1$ до $n$ расставлены по кругу. Начинаем отмечать числа $1,2,4,7,11,16,...$( общий член $1+k(k-1)/2(\bmod n)$). Значением функции $f(n)$ будет то число, которое первым будет отмечено повторно.
1. Найдите более явный вид $f(n).$
2. Найдите бесконечную последовательность чисел $n=n(k)$ (не обязательно всех), для которых $f(n)=n.$
3. Докажите, что для любого натурального $m$, существует бесконечно много значений $n$, для которых $f(n)=m.$

[Руст]

Задача эта из одного конкурса. Срок подачи решений истёк 22 февраля. Подробнее о предистории может сказать maxaл. Там приводятся много вопросов об этой функции, в том числе 2) и 3) не решённые автором. На самом деле решение 1, позволяет решить все остальные. Для начала приведу решение 1.
Занумеруем номера шагов отмечания $k$ нечётными числами $s=2k-1$. Тогда отмечаемый номер находится по формуле $(7+s^2(\bmod 8n))/8$. Некоторый номер отмечается дважды, если найдётся два нечётных числа $ s_1>s_2 \ge 1: \ s_1^2-s_2^2=0(\bmod 8n)$. Разница или сумма этих чисел делится на 2 и не делится на 4. Соответственно получается $s_1=pn_1+qn_2, \ s_2=|pn_1-qn_2|, \ n_2=\frac{2n}{n_1}, (2pn_1,8n)=2n_1,$ для некоторого нечётного делителя $n_1$. Первым повторно отмечается то число, которое получается при минимальным значении $s_1=n_1+\frac{2n}{n_1}, \ p=q=1$. Минимальное значение достигается в случае, когда в интервале $(n_1,n_2)$ нет нечётных делителей числа $n$. Таким образом, $f(n)$ вычисляется по формуле: $(7+s(n)^2(\bmod 8n))/8, \ s(n)=n_1+2n/n_1,$ где нечётный делитель определяется как нечётный делитель $n$ логарифм, которой ближе всего к $\ln(2n)/2$. или для которого $s(n)$ минимальное.

[Руст]

Приведу решение второй части:
Пусть $2n=xy,x=n_1, y=n_2$ соответствующее разложение искомого числа $n$. Легко проверить, что если удовлетворяется уравнение Пелля $x^2-2xy+y^2+7=4xy $ и в интервале $(x,y)$ нет других нечётных делителей $xy$, то $f(n)=n.$ Уравнение Пелля принимает вид $z^2-8y^2=-7$ после замены $z=|3y-x|$. Тривиальное решение $z=\pm 1,y=\pm 1$. Найдём образующую в группе единиц кольца $\mathbb{Z}[x,y\sqrt{8}]$. Это $(z,y)=3+\sqrt{8}$. Соответственно общее решение уравнения Пелля представляется в виде:
$z+y \sqrt 8=(\pm 1 \pm \sqrt8)(3+\sqrt 8)^k$. Соответственно, взяв нечётные $k$ для удовлетворения нечётности $x$, получаем решение в виде:
$x=2a-5b,y=a+b, a=\sum_{i=0}^k C_{2k+1}^{2i}3^{2k+1-2i}8^i, b=\sum_{i=0}^k C_{2k+1}^{2i+1}3^{2k-2i}8^i.$. Это соответствует нахождению чисел $x$ и $y$ по рекуренции:

[Руст]

В общем у этого направления решения недостатком является, то что нет гарантии, что между $x$ и $y$ нет нечётных делителей $xy$. Здесь я такой подход привёл, как подход, который приходит в голову первым.
Более эффективным подходом, является подход, когда n ищется делящемся на большое простое число $p$ (больше, чем $\sqrt{2n}$). в этом случае, автоматический нечётным делителем является $p$. Тогда из $p|n$, и из $s=P+2t$, получаем, что $(2t)^2+7$ делится на $8р$. При этом если $t$ является минимальным числом, для которого $s^2+7$ делится на $p$, то $n=pt$ удовлетворяет свойству $f(n)=n$. Таким образом, можно выбирать любое $p$, с условием $\left(\frac{-7}{p}\right)=1$, т.е $p=1,2,4 (\bmod 7)$. Найти минимальный чётный делитель (меньше $p$) $2t$ , такой, что $(p-2t)^2+7$ делится на $8p$, и взять $n=p(t,((p-2t)^2+7)/8)$. Такое $t$ определяет (заведомо) $f(n)$ если, $4t^2+7$ первое число делящееся на $p$. Т.е. это заведомо выполняется, если $4t^2+$ простое. Соответственно выбирая такие $t$ и простые числа $p$ вида $4t^2+7$ получаем $n=pt$, для которых $f(n)=n$. Согласно теореме Котофеича многочлен $4t^2+7$ принимает бесконечно много простых значений, которые обеспечивают бесконечно много значений $n$ с условием $n=pt,f(n)=n$.

[Руст]

3. Этот случай аналогичен 2 и проходит заменой числа $7$ на $7-8m$. В первом способе (поиск $n$ через $s(n)$) надо найти представление числа $8m-7$ в виде решения уравнении Пелля ( или, что то же самое) в виде нормы целого числа из кольца $\mathbb{Z}[\sqrt{8}].$ Такое представление всегда найдётся, однако остаётся проверять условие, что в интервале $(x,y)$ нет нечётных делителей числа $xy$. Это трудность преодолевается для конкретных значений, однако делает невозможным доказательство существования для любого $m$.
При втором подходе (через большой простой нечётный делитель $x=p$) эта задача решается успешнее и нахождение бесконечного числа значений $n$ со свойством $f(n)=m$ сводится к существованию бесконечного числа простых значений у многочлена $4t^2+c$ ($c=7-8m$ ). Согласно Котофеичу это верно.
К тому, же в первом подходе $n$ растёт експоненциально, а во втором примерно кубично (меньше чётвортой степени).
Эту задачу представлял в ответ просьбе sceptika, однако не нашёл отклика.