Делимость многочленов

[Ktina]

Найти все натуральные $k$, при которых многочлен $x^{2k+1}+x+1$ делится на многочлен $x^k+x+1$

[Sirion]

k таки равняется двум?

[sergei1961]

а просто углом поделить?

[Sirion]

sergei1961 в сообщении #526884 писал(а):

а просто углом поделить?

Если у Вас получится, можно ознакомиться с процессом и результатом?

Хотя, наверно, можно и так...

[Sonic86]

$x^k+x+1=\gcd(x^{2k+1}+x+1;x^k+x+1)=\gcd(x^{2k+1}+x+1-(x^k+x+1);x^k+x+1)=\gcd(x^{2k+1}-x^k;x^k+x+1)=\gcd(x^{k+1}-1;x^k+x+1)=\gcd(x^{k+1}-1-x(x^k+x+1);x^k+x+1)=\gcd(-1-x^2-x;x^k+x+1),$
значит $\deg (x^k+x+1)=\deg (x^2+x+1)$, ну и дальше понятно...

[sergei1961]

Всё-таки поделил по-простому углом. На третьем делении получается ненулевой многочлен третьей степени. Поэтому или остаток ненулевой, если $k>3$, или $k=0,1,2,3$, что перебирается руками ещё за пару минут.

[nnosipov]

sergei1961 в сообщении #527045 писал(а):

Всё-таки поделил по-простому углом. На третьем делении получается ненулевой многочлен третьей степени.

А можно и поумножать по-простому. Имеем $x^k \equiv -(x+1) \pmod{x^k+x+1}$, откуда $x^{2k+1}+x+1 \equiv x(x+1)^2+x+1=(x+1)(x^2+x+1) \pmod{x^k+x+1}$.

[ewert]

Попробую скрестить Sonic86 и sergei1961. Ясно, что для любого общего корня тех двух многочленов должно выполняться $x^{2k+1}=x^k$, т.е. $x^{k+1}=1$. Все корни многочлена $x^k+x+1$ -- простые, поэтому $x^{k+1}-1$ должен делиться на $x^k+x+1$. Ну это уже очевидно невозможно, если только $k\neq2$.

[nnosipov]

ewert в сообщении #527076 писал(а):

Ясно, что для любого общего корня ...

Рассмотрение корней --- явное излишество (корень --- в каком поле? ведь исходные многочлены можно считать заданными над произвольным полем; а конструкция поля разложения многочлена существенно сложнее, чем исходный вопрос о делимости). Вопросы делимости многочленов, как правило, решаются внутри того кольца многочленов, откуда они взяты, при этом обычно достаточно стандартных свойств взаимно простых многочленов (см. решение Sonic86). В нашем случае: поскольку $(x+1)(x^2+x+1) \equiv 0 \pmod{x^k+x+1}$ и $x+1$ --- неприводимый многочлен --- не делит $x^k+x+1$, получаем $x^2+x+1 \equiv 0 \pmod{x^k+x+1}$. И вот теперь действительно очевидно, что $k=2$.