Целочисленный полином

[Руст]

Пусть p(x) - целочисленный полином (принимающий целые значения при целыхаргументах) степени n. Доказать эквивалентность следующих условий:
(1) p(k)|p(m) тогда и только тогда, когда k|m;
(2) p(k)|p(m) если k|m;
(3) k|m если p(k)|p(m);
(4) существует целое число а, что $p(x)=ax^n$.

[Юстас]

Приведу схему доказательства: очевидно, верны импликации $ 1\rightarrow 2,\ 1\rightarrow 3,\ 4\rightarrow1,\ 2,\ 3$. Покажем $2\rightarrow 4,\ 3\rightarrow 4$.

$2\rightarrow 4:$ пусть отличен от нуля свободный член(иначе на степень $x$ можно сократить и рассмаривать то что останется), и пусть $x_2=kx_1$, тогда $p(x_1)|p(x_2)\ \forall k$. Рассмотрим $p(x_2)=p(kx_1)=q(k)$ как функцию от $k$. Имеем, $q(1)|q(k)\ \forall k$, тогда и $q(1)|q(q(1))$. Но $q(q(1))=q(1)*L+a_0, q(1)=\sum a_i$, где $a_i$-коэффициенты полинома $q$. Отсюда следует, что $a_0=0$, так как выбором $x_1$ сумму $\sum\limits_{i=1}^{i=n}a_i$ можно сделать сколь угодно большой. Для строгого рассуждения теперь нужно применить индукцию по deg P.
$3\rightarrow 4:$пусть $a_0\ne0$, $p(k)=n,\ (k, a_0)=1$, тогда и $(n, k)=1$. Имеем $p(k)|p(k+nt),\ t\in Z$, откуда по предположению $k|k+nt\ \forall t$-противоречие с тем что $a_0\ne 0$. Далее опять индукция.

[nworm]

Юстас писал(а):

$3\rightarrow 4:$пусть $a_0\ne0$, $p(k)=n,\ (k, a_0)=1$, тогда и $(n, k)=1$. Имеем $p(k)|p(k+nt),\ t\in Z$, откуда по предположению $k|k+nt \forall t$-противоречие с тем что $a_0\ne 0$. Далее опять индукция.

А можно пояснить, почему мы имеем

Юстас писал(а):

$p(k)|p(k+nt),\ t\in Z$

и как дальше идёт индукция.

[Юстас]

Если расписать выражение для $p(k+nt)$ по биному, то выделится $p(k)=n$ и сумма, каждый член которой делится на $n$. Далее, если $a_0=0$, то выносите $x$ в максимально возможной степени за скобки, и останется полином меньшей степени - примените предположение индукции.

[Руст]

Я не вижу доказательство утверждения. Можно принять только равенство нулю свободного члена.

[Юстас]

Да, сразу из равенства нулю свободного члена решение не получается. Постараюсь дополнить: итак, вынесем у исходного полинома общий множитель $x$ в максимально возможной степени и предположим, что у оставшегося многочлена меньшей степени $p_1(x)$ свободный член $a$ не равен 0.
Доказываем импликацию $2\rightarrow4\ :$
Имеем: $\frac{p(kx_1)}{p(x_1)}=\frac{k^\alpha p_1(kx_1)}{p_1(x_1)}$. Считаем, что коэффициенты $p_1(x)$ в совокупности взаимнопросты(иначе вынесем общий множитель за скобки). Пусть $x_2=kx_1,\ p_1(kx_1)=q(k)$.
1) Выберем $x_1$ так, чтобы $(a, q(1))=1 $, $q(1)$ - не простое.
2)Рассмотрим сравнение $q(k)\equiv0(mod\ q(1))$. Так как $q(1)$ - составное, и $(a, q(1))=1$, то сравнение имеет не более $q(1)-2$ решений, то есть существует $0<x_0<q(1):\ q(x_0+tq(1))$ не делится на $q(1)$ для любого $t$.
3)Положим $k=x_0$. Посмотрев теперь на $\frac{p(kx_1)}{p(x_1)}$, видим, что это число не целое, поэтому свободный член $p_1$ есть $a=0$ и нужное представление получено.
Вторую импликацию напишу чуть позже.

[Юстас]

насчет импликации $3\rightarrow4\ :$(в обозначениях предыдущего поста)выберем простое $l$ так, что для некоторого $x_0$ $p_1(x_0)$ делится на $l^{\alpha}$ и $(p_1(l), l)=1$(возможно в предположении ненулевого свободного члена $p_1(x)$). Далее, $p_1(l+tp_1(l))$ делится на $p_1(l)\ \forall t$. Так как $(p_1(l), l^{\alpha})=1$, то существует $d: $ $p_1(d)$ делится на $p_1(l)l^{\alpha}$. Осталось понять, почему такое $d$ можно всегда выбрать не делящимся на $l$, чтобы получить противоречие.

[Юстас]

Неужели я написал такую глупость, что никто ничего не сказал? Или все непонятно?

[juna]

Если $a_n, a_{n-1},...$ коэффициенты многочлена $p(x)$, то из $p(k)|p(m)$, следует, что $\text{НОД}(a_n,a_{n-1},...)=1$, а поскольку доказали, что свободный член равен нулю, то должно быть $k|m$.

[Юстас]

Артамонов Ю.Н. писал(а):

Если $a_n, a_{n-1},...$ коэффициенты многочлена $p(x)$, то из $p(k)|p(m)$, следует, что $\text{НОД}(a_n,a_{n-1},...)=1$, а поскольку доказали, что свободный член равен нулю, то должно быть $k|m$.

Не понятно, к чему это относится. Вообще, я писал:

Юстас писал(а):

вынесем у исходного полинома общий множитель $x$ в максимально возможной степени и предположим, что у оставшегося многочлена меньшей степени $p_1(x)$ свободный член $a$ не равен 0.

И дальше почти везде фигурирует $p_1(x)$.

[juna]

Извиняюсь, я неправильно понял условие. Я и сейчас его не понимаю. Например, $p(x)=x^3+x^2+x+11$, тогда $p(3)=2p(2)$, но $2|3$ - ложь.

[Руст]

Артамонов Ю.Н. писал(а):

Извиняюсь, я неправильно понял условие. Я и сейчас его не понимаю. Например, $p(x)=x^3+x^2+x+11$, тогда $p(3)=2p(2)$, но $2|3$ - ложь.

А что же непонятного. Тут ведь не многочлен вида 4). Как раз согласно 3) если многочлен не такого вида, то дожны существовать значения p(m)|p(n) и в то же время m не делит n.

[juna]

Пусть $p(x)=c_nx^n+c_{n-1}x^{n-1}+…+c_1x+c_0$ и пусть $p(m)=p(k)l$, тогда имеем $c_n(m^n-lk^n)+c_{n-1}(m^{n-1}-lk^{n-1})+…+c_1(m-lk)=c_0(l-1)$. Выбираем заведомо любые $c_n,c_{n-1}…,c_1$ и $l$ а также какие хотим $m,k$ - хоть делящие один другого, хоть нет находим $c_0$. Допустим выбрали неделящимися, получили соответствующий многочлен $p_1(x)$. Теперь нужно доказать, что если он отличен от $cx^n$ для него существуют такие делящиеся $m_1,n_1$, что $p_1(n_1)|p_1(m_1)$. Для этого берем $m_1=A(p_1(A)+1)$, $n_1=A$, тогда $p_1(A)|p_1(A(p_1(A)+1))$ и $n_1|m_1$.

[Юстас]

Артамонов Ю.Н. писал(а):

Теперь нужно доказать, что если он отличен от $cx^n$ для него существуют такие делящиеся $m_1,n_1$, что $p_1(n_1)|p_1(m_1)$.

Нужно доказать, что если он отличен от $cx^n$ для него существуют такие делящиеся $m_1,n_1$, что $p_1(n_1)$ не делит $p_1(m_1)$.

[juna]

Условие, что для многочлена, отличного от $cx^n$ всегда существуют такие $n_1|m_1$, что $p_1(n_1)\not |p_1(m_1)$ сводится к тому, что если бы оно не выполнялось, то существовал бы многочлен вида $h(k)=c_nc_0^{n-1}k^{n}+c_{n-1}c_0^{n-2}k^{n-1}+…c_1k+1$, $m_1=kc_0$, $n_1=c_0$, что $\forall k \text{ }h(1)|h(k)$ - но это уж слишком для натуральных $c_i$, для целых должно быть $c_nc_0^{n-1}+c_{n-1}c_0^{n-2}+...+c_1 = 0$. Пусть оно выполняется. Проще показать показателя $n=2$, тогда должно быть $c_2c_0+c_1=0$. При этом условии берем следующие $m_1=kc_0^3$, $n_1=c_0^3$, тогда должно быть $c_2c_0^5+c_1c_0^2=0$ или $c_2c_0^3+c_1=0$, что противоречит $c_2c_0+c_1=0$. Мне кажется, Руст расширяет условия задачи ссылка

Ссылки стоит прятать в тег [url]. Иначе корректные ссылки автоматически распознаются форумом и форматируются. // нг