алгебра - Найти натуральное n такое, что данный многочлен является делителем x^n + 1

Пусть многочлен $%f(x)$% неприводим над полем $%F=\mathbb Z_2$%. Тогда факторкольцо $%F[x]/(f(x))$% по главному идеалу является полем. Если степень многочлена равна $%n$%, то поле состоит из $%2^n$% элементов. Порядок мультипликативной группы равен $%2^n-1$%, поэтому $%x^{2^n-1}=1$% для любого элемента поля кроме нуля. Отсюда следует, что любой элемент поля удовлетворяет уравнению $%x^{2^n}-x=0$%. Из теоремы Безу следует, что многочлен раскладывается на линейные множители над этим полем. То есть корни этого многочлена -- в точности все элементы поля.

Рассмотрим НОД многочленов $%f(x)$% и $%x^{2^n}-x$% над основным полем. Он делит $%f(x)$%, и ввиду неприводимости, НОД равен 1 или $%f(x)$%. Первый случай невозможен, так как $%f(x)$% имеет корень в расширении поля (это класс вычетов многочлена $%x$%). Значит, $%x(x^{2^n-1}-1)$% делится на $%f(x)$%, а потому $%f(x)$% делит $%x^{2^n-1}-1$%. В нашем случае $%x^4+x+1$% делит $%x^{15}+1$% ("минус" и "плюс" для поля характеристики 2 -- одно и то же).

Этот факт можно сформулировать в виде олимпиадной задачи (она где-то предлагалась). Есть бесконечная линия из лампочек, на них можно одновременно нажимать при помощи "расчёски" с выломанными зубцами. В нашем случае это будут лампочки под номерами $%n$%, $%n+1$%, $%n+4$%. Изначально ни одна лампочка не горит; надо доказать, что после нескольких нажатий можно зажечь ровно 2 лампочки. В этом легко непосредственно убедиться, делая следующее. Сначала зажигаем лампочки с номерами 0, 1, 4. Далее левым краем "расчёски" касаемся лампочки 1, меняя статус лампочек 1, 2, 5. После этого у нас горят номера 0, 2, 4, 5. Лампочку 0 не трогаем, и начинаем с лампочки 2, меняя статус лампочек 2, 3, 6. И так далее. Это однозначный процесс, в ходе которого мы зажжём 0 и 15, в чём можно убедиться, делая рисунки.

По поводу $%g(x)$%: это произведение двух неприводимых над $%F$% многочленов, первый из которых делит $%x^{15}-1$%, а второй $%x^7-1$%. Ввиду того, что $%x^{mn}-1$% всегда делится на $%x^m-1$%, получаем, что $%x^{105}-1$% делится на оба многочлена, а потому и на их произведение, так как они неприводимы и различны.