Question

При каких натуральных n и k многочлен x^n-1 делится без остатка на многочлен x^k-1?

Answer 1

Очевидно ,  что многочлен меньшей  степени не  может делится на  больший ,  тогда n>=k .

Таким образом можно записать :

n=m*k +t  t-остаток от деления n  на k    ( t=0,1,2,3....k-1)  ( t<k)

Запишем :

x^n-1 = x^(m*k+t) -1 = x^(m*k) * x^t  -1 =  x^(m*k) *x^t -x^t +x^t -1 =

= x^t*( x^(m*k) -1 )  +(x^t -1)

Многочлен : x^t*( x^(m*k) -1 )   делится на  x^(k) -1  поскольку если поделить на x^k-1  многочлен в скобках получаем геометрическую прогрессию  :

(x^(m*k) -1 )/(x^(k) -1) = 1+x^k +x^2k ... +x^k*(m-1)

Пусть остаток  t≠0

Тогда  поскольку t < k ,  то   x^t -1 не делится на x^k -1  .

А  значит очевидно,что   весь многочлен :

x^t*( x^(m*k) -1 )  +(x^t -1)  не делится на  x^k -1

Таким  образом x^n-1  делится  на x^k-1 ,  только  когда  остаток t=0.

Иначе говоря n должно  делится на k

Answer 2

Многочлен x^n - 1 делится без остатка на многочлен x^k - 1, если и только если n делится на k.

Это можно доказать, рассмотрев деление многочленов с помощью длинной деления. При делении многочлена x^n - 1 на многочлен x^k - 1 получаем остаток, который также должен быть равен нулю для деления без остатка.

Однако, если n не делится на k, то многочлен x^n - 1 не делится без остатка на многочлен x^k - 1. Это можно увидеть, рассматривая остатки при делении многочленов.

Таким образом, для того чтобы многочлен x^n - 1 делился без остатка на многочлен x^k - 1, необходимо и достаточно, чтобы n было кратно k.