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

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

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

n=m*k +t  t-остаток от деления n  на k    ( t=0,1,2,3k-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