При каких натуральных n и k многочлен x^n-1 делится без остатка на многочлен x^k-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