Главная
Каталог задач
Каталог заданий по Олимпиады - Математика
Неприводимость и разложение на неприводимые многочлены

Тема Многочлены

Неприводимость и разложение на неприводимые многочлены

Вспоминай формулы по каждой теме

Решай новые задачи каждый день

Вдумчиво разбирай решения

ШКОЛКОВО.
Готовиться с нами - ЛЕГКО!

Подтемы раздела многочлены

Решаем задачи

Ошибка.
Попробуйте повторить позже

Задача 1#121043

Докажите, что для любого простого $p$ существует ровно $p3+p- 2$ неприводимых над $𝔽 p$ многочленов степени не выше $2.$

Показать ответ и решение

Всего имеется $p3$ многочленов степени не выше $2$ над $F p$ (для каждого из трёх коэффициентов по $p$ вариантов). Давайте теперь посчитаем количество приводимых. Каждый приводимый многочлен имеет вид либо $a(x− b)(x − c),$ где $a$ — ненулевой вычет, а $b$ и $c$ — произвольные вычеты. Приводимых многочленов второй степени всего $2 Cp(p − 1)+ p(p− 1)$ (суммы случаев, когда корни разные и одинаковые). Значит, количество неприводимых многочленов равно

3 2 p3+ p p − C p(p− 1)− p(p− 1)=-2--

Ответ:

$p3+p 2$

Бандлы и наборы

Комбо-тарифы сразу по нескольким предметам

Ошибка.
Попробуйте повторить позже

Задача 2#121115

(a) Лемма Гаусса. Докажите, что для любых многочленов $P (x),$ $Q(x)$ с целыми коэффициентами верно $cont(P ⋅Q )=cont(P)⋅cont(Q).$

(b) Многочлен $P(x)∈ ℤ[x]$ неприводим над $ℚ$ тогда и только тогда, когда он неприводим над $ℤ.$

Показать доказательство

(a) Нетрудно заметить, что $cont(P ⋅Q)$ делится на $cont(P)⋅cont(Q ).$ Теперь докажем, что $cont(P)⋅cont(Q)$ делится на $cont(P ⋅Q).$ Пусть $cont(P ⋅Q )$ делится на некоторое простое $p,$ то есть равно $0$ в $Fp.$ Но тогда какой-то из многочленов $P,Q$ равен $0$ в $Fp,$ а значит, $cont(P)⋅cont(Q )$ делится на $p,$ то есть в рассматриваемой делимости на $p$ можно делимое и делитель сократить. Так мы сократим все простые числа, входящие в $cont(P ⋅Q ),$ то есть делимость доказана. Если два числа друг на друга делятся, то они равны.

(b) Достаточно доказать, что мнонгочлен $P$ приводим над $ℚ$ тогда и только тогда, когда он приводим над $ℤ.$ Понятно, что из приводимости над $ℤ$ приводимость над $ℚ$ автоматически следует. Теперь докажем обратное. Пусть $P = QR,$ где $Q$ и $R$ — многочлены с рациональными коэффициентами. Пусть $n1$ — НОК знаменателей $Q,$ $n2$ — НОК знаменателей $R.$ Тогда $n1n2P =n1Q ⋅n2R.$ Пусть $cont(n1Q)= x,cont(n2R)= y,n1Q = xQ1,n2R = yR1,$ где $Q1$ и $R1$ — целочисленные многочлены с единичным содержанием. Ясно, что $xy$ делится на $n1n2.$ Значит, можно сократить на $n1n2$ и получить приводимость над $Z.$

Ошибка.
Попробуйте повторить позже

Задача 3#121123

Критерий Эйзенштейна. Пусть все коэффициенты $P(x)∈ ℤ[x],$ кроме старшего, делятся на простое число $p,$ и свободный член не делится на $2 p.$ Тогда $P (x)$ неприводим над $ℤ.$

Показать доказательство

Пойдём от противного, пусть $P$ приводим над $ℤ :$ $P(x) =Q (x)⋅R(x).$ Рассмотрим эти многочлены в $F . p$ По условию $P(x)$ в $F p$ будет иметь вид $n ax ,$ где $n≥ 1,$ потому что остальные коэффициенты кратны $p.$ Но тогда каждый из многочленов $Q$ и $R$ будут иметь такой же вид. Значит, их свободные члены в $Fp$ равны $0,$ но тогда в $ℤ$ они кратны $p.$ В этом случае свободный член $P$ будет делиться на $2 p .$ Пришли к противоречию.

Ошибка.
Попробуйте повторить позже

Задача 4#122886

Многочлен $P(x)$ с целыми коэффициентами неприводим над $ℤ.$ Докажите, что у многочлена нет кратных действительных корней.

Показать доказательство

Предположим, что существует неприводимый над $ℤ$ многочлен $P (x)∈ ℤ[x],$ имеющий кратный корень. Тогда у многочлена $′ P (x)$ тоже есть этот корень, где $′ P (x)$ — производная $P(x).$ Пусть $′ D (x)= НО Д(P(x),P(x)).$ Тогда $D (x)∈ ℚ[x]$ и

′ deg P(x)>deg P (x)≥deg D (x)> 0,

так как у $P(x)$ и $P′(x)$ есть общий корень. Но тогда $P(x)$ приводим, так как делится на многочлен меньшей ненулевой степени с рациональными коэффициентами.

Ошибка.
Попробуйте повторить позже

Задача 5#74870

Многочлен седьмой степени с целыми коэффициентами в семи целых точках равен $± 1.$ Докажите, что его нельзя представить в виде произведения двух непостоянных многочленов с целыми коэффициентами.

Показать доказательство

Предположим противное. Пусть $p(x)$ – наш многочлен, и $p(x)= q(x)⋅r(x),$ где $q,r ∈ℤ[x]$ и $1≤ deg(q), deq(r)≤ 6.$ По принципу Дирихле, степень одного из $q$ и $r$ не превосходит $3.$ Пусть, не умаляя общности, $deg(q)≤ 3.$ Так как $q$ и $r$ принимают целые значения в целых точках, их значения в выделенных семи точках $a1,...,a7$ равны $1$ по модулю. По принципу же Дирихле, одно из значений $1,−1$ многочлен $q$ принимает хотя бы в $4$ точках. Не умаляя общности, пусть это $− 1.$ Тогда многочлен $q+ 1$ имеет степень не больше $3$ и хотя бы $4$ различных корня – противоречие.

Ошибка.
Попробуйте повторить позже

Задача 6#74871

Докажите для различных целых $a ,a,...,a 1 2 100$ неприводимость многочлена

(x− a1)(x− a2)...(x− a100)− 1

Показать доказательство

Поскольку приводимость над $Q$ равносильна приводимости над $Z,$ достаточно доказывать неприводимость многочлена над $Z.$ Обозначим его символом $p,$ и предположим, что $p(x)= q(x)⋅r(x),$ где $q,r ∈ℤ[x]$ и $1≤ deg(q), deq(r) ≤99.$ Отметим, что в точках $a1,...,a100$ наш многочлен принимает значение $− 1.$ Тогда в точках $a1,...a100$ и $q(x),$ и $r(x)$ принимают значения по модулю равные $1,$ причем, поскольку их произведение отрицательно, они различны по знаку. Рассмотрим $q(x)+r(x).$ Степень этого многочлена не превосходит $99,$ но в ста точках $a1,...,a100$ он принимает значение $0.$ Такое возможно только если $q(x)+r(x)$ тождественно равен $0,$ то есть $q(x) =−r(x).$ Но тогда $2 p(x)= q(x)⋅r(x)= −q (x)$ имеет отрицательный старший коэффициент, однако очевидно, что $p(x)= (x − a2)...(x− a100)− 1$ имеет положительный старший коэффициент – противоречие.

Курсы

Всё необходимое для достижения цели

Ошибка.
Попробуйте повторить позже

Задача 7#75625

Разложите в произведение неконстантных многочленов над $ℤ 3$ многочлен $x3+ x+ 1.$

Подсказки к задаче

Подсказка 1

Нужно разложить многочлен третей степени. Какие степени могут быть у множителей?

Подсказка 2

Надо сделать произведение линейной и квадратных функций. Как их можно подобрать? Легче найти линейный множитель. Пусть он x - a, тогда при подстановке a в многочлен будет ноль. Переберите остатки и найдите a, затем, выполнив деление, найдите требуемое разложение.

Показать ответ и решение

Над $ℤ 3$

3 3 3 x +x +1 =x + x− 2= (x − 1)+ (x− 1)=

2 2 = (x− 1)(x +x +1)+ (x − 1)= (x− 1)(x +x+ 2)

Ответ:

$(x− 1)(x2+ x+2)$

Ошибка.
Попробуйте повторить позже

Задача 8#75626

Пусть $P(x),Q (x)∈ ℤ [x] p$ ( $p$ — простое число). При этом для любого $a ∈ℤ p$ выполнено $P(a)= Q(a).$ Докажите, что $P(x)− Q(x)$ делится на $p x − x.$

Показать доказательство

Из условия следует, что многочлен $P(x)− Q (x)$ имеет корни $0,1,...,p− 1.$ Тогда по теореме Безу получаем, что $P(x)− Q (x)$ делится на $x(x− 1)...(x− (p− 1)).$

Так как над $ℤp$ все многочлены вида $x,x− 1,...,x− (p− 1)$ различны и неприводимы, то верно равенство $p x(x− 1)...(x − (p− 1))= x − x,$ которое приводит к нужному результату.

Ошибка.
Попробуйте повторить позже

Задача 9#75648

Даны многочлен $P(x)$ с целыми коэффициентами и натуральное число $n.$ Старший коэффициент и свободный член многочлена $P(x)$ взаимно просты с $n,$ остальные коэффициенты делятся на $n.$ Известно, что многочлен $P(x)$ делится на $2 Q (x)$ для некоторого многочлена $Q (x)$ ненулевой степени. Докажите, что степень $P(x)$ делится на $n.$

Подсказки к задаче

Подсказка 1

Во-первых, Q всегда можно заменить на его неприводимый множитель, если сам Q не является неприводимым. А можно ли свести задачу к случаю, когда Q рационален?

Подсказка 2

Можно! Для этого достаточно показать, что если Q₁ — минимальный многочлен с рациональными коэффициентами, делящийся на Q, то P(x) делится на квадрат многочлена Q₁. Как это сделать?

Подсказка 3

Верно! Для начала нужно показать, что если многочлен с рациональными коэффициентами делится на Q, то он делится и на Q₁ (это легко сделать простым делением с остатком). А что будет, если теперь рассмотреть частное P и Q₁?

Подсказка 4

Точно! Если Q² не делит Q₁, то это будет означать, что многочлен с рациональными коэффициентами, равный частному P и Q₁, делится на Q! А это уже означает, что он делится на Q₁, и мы докажем заявленное утверждение. А как показать, что Q₁ не делится на квадрат Q?

Подсказка 5

Конечно! В противном случае производная многочлена Q₁, имеющая рациональные коэффициенты, делится на Q, следовательно, делится и на Q₁, а это невозможно, ведь Q₁ непостоянный! Итак, можно считать, что Q имеет рациональные коэффициенты. А можно ли теперь вообще считать, что Q имеет целые коэффициенты?

Подсказка 6

Можно! Для этого нужно просто аккуратно вынести знаменатели из равенства P(x) = Q²(x)R(x), чтобы получить произведение многочленов с целыми коэффициентами, а потом вынести содержание. Полученная константа перед произведением, очевидно, целая. Понятно, что для решения задачи достаточно доказать, что производная P делится на n. А как можно удобно представить производную P?

Подсказка 7

Верно! Легко заметить, что P' = QS, где Q и S — многочлены с целыми коэффициентами. Можно ли теперь, используя знания о многочлене P, доказать, что все коэффициенты S делятся на n?

Показать доказательство

Будем полагать, что $Q$ — неприводим над $ℝ$ (в противном случае вместо $Q$ можно рассмотреть его неприводимый множитель $∼ Q ).$

Покажем, что можно считать, что $Q$ — многочлен с рациональными коэффициентами. Действительно, пусть $Q1(x)$ — многочлен минимальной степени с рациональными коэффициентами, такой, что $Q|Q1$ (такой многочлен существует, поскольку $Q |P).$

Заметим, что любой многочлен $F ∈ ℚ[x],$ делящийся на $Q (x),$ делится и на $Q1(x).$ Для того, чтобы это доказать, разделим $F$ на $Q1$ с остатком: $F = AQ1+ B.$ Все участвующие в этом равенстве многочлены, очевидно, имеют рациональные коэффициенты. Так как $Q |F$ и $Q |Q1,$ а потому $B$ делится на $Q,$ однако его степень меньше, чем степень многочлена $Q1$ и, следовательно, $B ≡ 0.$

Многочлен $Q1$ не может делиться на $Q2,$ поскольку в ином случае $Q(x)|Q′1(x),$ при этом многочлен $Q1$ имеет рациональные коэффициенты, поэтому и многочлен $Q′1 ∈ ℚ[x].$ По доказанному выше это означает, что $Q1|Q′1,$ что невозможно, если $Q1$ не $0$ (из соображения о том, что $degQ1 > degQ ′1).$ Но тогда $Q1 ≡ const,$ а это не так, поскольку $Q⁄≡ const.$

Рассмотрим многочлен, равный частному $P$ и $Q1.$ Он имеет рациональные коэффициенты и делится на $Q$ (так как $Q$ — неприводимый, при этом $Q2$ не делит $Q1,$ но делит $P).$ Тогда частное многочленов $P$ и $Q1$ делится на $Q1,$ следовательно, $P$ делится на $Q21.$ Таким образом, мы нашли многочлен $Q1$ с рациональными коэффициентами, на квадрат которого делится $P.$ Таким образом, можно изначально полагать, что $Q ∈ ℚ[x].$

Итак, имеем равенство $P(x)= Q2(x)R(x),$ где $Q,R ∈ℚ [x],$ $P ∈ ℤ[x].$ Приведем коэффициенты $Q$ и $R$ к общим знаменателям $DQ$ и $DR.$ Тогда имеем равенство

P(x)= --1--Q22(x)R2(x) D2QDR

где $Q2,R2 ∈ℤ[x].$ После этого из каждого многочлена $Q2$ и $R2$ вынесем $cont(Q2)$ и $cont(R2).$ Получим равенство

cont(Q2)2cont(R2) P(x)= -----D2DR-----Q23R3 Q

Поскольку $contQ3 = 1$ и $contR3 =1,$ константа, стоящая в последнем равенстве перед произведением этих многочленов, должна быть целой. Тогда положим

R4 = R3⋅ cont(Q2)2cont(R2) D2QDR

и получим равенство $P(x) =Q2(x)R (x), 3 4$ где $Q ,R ∈ℤ[x]. 3 4$ Тогда можно полагать, что $Q ∈ ℤ[x].$

Очевидно, что младший коэффициент $Q$ взаимно прост с $n.$ Заметим, что $′ 2 ′ ′ 2 ′ P =(Q R) = 2QQ R+ Q R = QS,$ где $S ∈ ℤ[x].$ Докажем, что все его коэффициенты делятся на $n.$ Предположим, что это не так. Рассмотрим одночлен многочлена $S$ минимальной степени, который не делится на $n$ и положим, что его степень равна $r.$ Тогда $′ r <degP ,$ так как $P$ — многочлен ненулевой степени. Коэффициент $QS$ при одночлене степени $r$ не делится на $n,$ так как младший коэффициент $Q$ взаимно прост с $n$ (остальные слагаемые делятся), но у многочлена $′ P$ коэффициент при одночлене степени $r$ делится — противоречие.

Значит, и старший коэффициент $′ P$ делится на $n.$ Этот коэффициент равен $CdegP,$ где $C$ — старший коэффициент $P.$ Поскольку $(C,n)= 1$ по условию, то $deg P$ делится на $n.$

Ошибка.
Попробуйте повторить позже

Задача 10#75796

Даны многочлены $P,Q ∈ℚ [x].$ Рассмотрим НОДы этих многочленов над $ℚ$ и над $ℝ.$ Докажите, что эти НОДы отличаются домножением на константу.

Показать доказательство

В $ℚ$ $НОД(P,Q)$ находится алгоритмом Евклида. Ясно, что этот же алгоритм подойдет и в $ℝ.$ Но тогда $НОД (P,Q) ℚ$ отличается домножением на константу от $Н ОДℝ(P,Q),$ что и требовалось доказать.

Ошибка.
Попробуйте повторить позже

Задача 11#75798

Разложите $x12− 1$ на неприводимые сомножители ненулевой степени с целыми коэффициентами.

Показать ответ и решение

По формуле разности квадратов

12 6 6 x − 1 =(x − 1)(x +1)

Преобразуем отдельно каждую скобку.

По формуле разности квадратов

6 3 3 x − 1= (x − 1)(x + 1)

Далее применим формулы сумму и разности кубов

3 3 2 2 (x − 1)(x + 1)= (x − 1)(x + x+ 1)(x+ 1)(x − x+1)

Разложим теперь $x6+ 1.$ По формуле суммы кубов

x6 +1= (x2+ 1)(x4− x2+ 1)

Получаем, что $x12− 1 =(x− 1)(x2+ x+1)(x +1)(x2 − x+ 1)(x2+ 1)(x4− x2 +1).$

Очевидно, что $x− 1$ и $x +1$ неприводимы над $ℤ.$ Квадратные трехчлены $x2+ x+ 1$ и $x2− x +1$ тоже неприводимы над $ℤ,$ так как если бы они были приводимы, то имели бы корни, которых у них нет, так как их дискриминант равен -3. Аналогично, $x2+1$ — неприводим.

Осталось проверить, что $4 2 x − x + 1$ неприводим над $ℤ.$ Понятно, что он не может раскладываться в виде $3 2 (x− x0)(x +ax + cx+ d),$ так как тогда бы у него был целый корень, однако все его корни комплексные. Тогда единственный возможный вариант разложения — это $2 2 (x + ax +b)(x + cx+ d).$ Покажем, что и это невозможно. Для начала раскроем скобки и сгруппируем.

(x2+ ax+ b)(x2 +cx+ d)=x4 +(a+ c)x3+ (b+ d+ ac)x2+ (ad+ bc)x+ bd

Тогда, так как полученный многочлен должен быть тождественно равен исходному, получаем систему уравнений в целых числах на коэффициенты:

(| |||{ a +c= 0 | b+ d+ ac= −1 |||( ad+ bc= 0 bd= 1

Из последнего уравнения получаем $b= d= ±1,$ так как $b,d∈ ℤ.$ Тогда из второго получаем $ac= −3$ или $ac =1.$ Заметим, что оба варианта невозможны, так как целых решений вместе с уравнением $a+ c=0$ быть не может. Тогда получаем, что $x4− x2 +1$ действительно неприводим.

Ответ:

$(x− 1)(x2+ x+1)(x +1)(x2 − x+ 1)(x2+ 1)(x4− x2 +1)$

Интенсивы

Глубокий разбор тем, требующих дополнительного внимания

Ошибка.
Попробуйте повторить позже

Задача 12#75799

Даны взаимно простые многочлены $P$ и $Q$ с целыми коэффициентами, то есть $(P,Q)= 1$ над $ℝ.$ Докажите, что существует такая константа $C,$ что для любого целого $k$ выполнено $(P(k),Q(k))< C.$

Показать доказательство

Заметим, что из взаимной простоты многочленов в $ℝ$ следует их взаимная простота в $ℚ$ (иначе они бы не были взаимно простыми в $ℝ$ ). Тогда понятно, что на самом деле можно решать задачу в $ℚ,$ так как $P, Q ∈ ℚ[x].$

Тогда, так как многочлены $P$ и $Q$ взаимно просты для некоторых многочленов $A, B ∈ ℚ[x]$ имеет место тождество $P (x)A(x)+ Q(x)B (x)= 1.$ Так как коэффициенты многочленов $A$ и $B$ рациональны, можно умножить уравнение на $D,$ равное наименьшему общему кратному всех знаменателей этих многочленов.

Тогда получаем новое тождество $P(x)(DA(x))+Q(x)(DB (x))= D,$ в котором многочлены $P, DA = A1, Q, DB =B1$ имеют целые коэффициенты. Пусть $k ∈ℤ.$ Тогда верно равенство $P(k)A1(k)+Q (k)B1(k)= D.$ То есть уравнение $xP (k)+ yQ(k)= D$ имеет решение $(A1(k),B1(k))$ в целых числах. Но тогда $НОД (P(k),Q (k)) | D.$ Тогда получаем, что $НО Д(P(k),Q(k))≤ D$ для любого целого $k.$ В качестве требуемой константы $C$ берем $D + 1.$ Таким образом, её существование доказано.

Ошибка.
Попробуйте повторить позже

Задача 13#75800

Докажите, что многочлен $11x11 +10$ неприводим над $ℚ.$

Показать доказательство

Используем критерий Эйзенштейна: Пусть все коэффициенты $P(x)∈ℤ[x],$ кроме старшего, делятся на простое число $p,$ и свободный член не делится на $2 p .$ Тогда $P(x)$ неприводим над $ℤ$ (а значит и над $ℚ$ ).

Для многочлена из нашей задачи $2⁄| 11$ — старший коэффициент, $2 | 10$ и $2 2 =4 ⁄| 10$ — свободный член, который является единственным коэффициентом, кроме старшего.

Ошибка.
Попробуйте повторить позже

Задача 14#75801

(a) Докажите, что многочлен $2016 x − 1$ раскладывается над $𝔽2017$ в произведение нескольких многочленов вида $7 x − a$ для $a ∈𝔽2017;$

(b) Можно ли натуральные числа $1,2...,2016$ можно разбить на группы по $7$ так, чтобы сумма чисел в каждой семерке делилать на $2017?$

Показать ответ и решение

(a) Рассмотрим все возможные ненулевые вычеты по модулю $2017.$ Пусть $g$ — первообразный корень. Тогда эти вычеты имеют вид $1 2016 g ,...,g .$ Возведем их в $7$ степень. Тогда получим набор $7 1 7 2016 (g ),...,(g) .$ Заметим, что $2016$ делится на $7,$ и частное равно $288.$ Тогда легко видеть, что $7 ordpg = 288.$ Из этого получаем, что сравнение $7 x − a≡p 0$ имеет решения $r r+288 r+6⋅288 g,g ,...,g$ для $7r g ≡p a.$ Таким образом, все решения сравнения $2016 x − 1≡p 0$ являются решениями одного из сравнений вида $7 x − a≡p 0,$ откуда вытекает требуемое.

(b) Будем воспринимать данный набор чисел, как набор ненулевых остатков по модулю $2017.$ Так как число $2017$ — простое, то существует первообразный корень по модулю $2017.$ Пусть $y$ — некоторый первообразный корень по модулю $2017.$ Пусть $t≡y288 (mod 2017).$ Заметим, что $t7− 1 ≡0 (mod 2017)$ — по малой теореме Ферма. Преобразуем это сравнение:

t7− 1 ≡0 (mod 2017)

(t− 1)(t6+ t5+ t4+t3+ t2 +t+ 1)≡0 (mod 2017)

Заметим, что $t⁄≡ 1 (mod 2017),$ так как $y$ — первообразный корень. Это значит, что $6 5 4 3 2 t +t + t+ t +t + t+1≡ 0 (mod 2017).$

Тогда разделим все числа на $288$ групп вида $2 3 4 5 6 a,at,at ,at,at,at,at,$ где $a$ некоторый ненулевой остаток по модулю $2017.$ Проверим, что сумма этих чисел делится на $2017 :$

a+ at+at2+ at3+ at4 +at5+at6 = a(1+ t+ t2+ t3+t4+ t5+ t6)≡ 0 (mod 2017)

Теперь покажем, что все числа различны. Допустим, что два числа совпали внутри группы. Тогда имеем

atm ≡ atn (mod 2017)

a(tm − tn)≡ 0 (mod 2017)

Тогда получаем, что $m n t ≡ t (mod 2017).$ Будем считать, что $m ≥n.$ Тогда, так как $2017$ — простое, имеем $m−n t ≡1 (mod 2017).$ При этом $m,n< 7,$ тогда $(m−n,7) t ≡ 1 (mod 2017).$ Так как $7$ — простое, то $t≡ 1 (mod 2017),$ но это противоречит тому, что $y$ первообразный корень.

Допустим, теперь, что числа из разных групп совпали. Это эквивалентно сравнению $axm ≡bxn (mod 2017).$ Но тогда мы получаем, что $b≡ axm−n (mod 2017),$ то есть $b$ — число из группы $a,at,at2,at3,at4,at5,at6,$ однако мы предполагали, что числа из разных групп — противоречие.

Итак, мы получили разбиение, требуемое условием задачи.

Ответ:

$b)$ Да, можно

Ошибка.
Попробуйте повторить позже

Задача 15#75802

Разложите на неприводимые над $ℚ$ множители многочлен $x2017− 32017.$

Показать ответ и решение

По формуле сокращенного умножения $x2017 − 32017 = (x− 3)(x2016+3x2015+ ...+ 32015x+32016).$ Пусть $P(x)=x2016+ 3x2015+ ...+ 32015x +32016.$ Докажем, что он неприводим.

Пусть $x= 3y.$ Тогда получаем $2016 2015 2015 2016 2016 2016 2015 x + 3x +...+ 3 x+ 3 =3 (y + y +...+ y+ 1).$

Теперь снова сделаем замену $y = t+1.$ Тогда в скобке имеем многочлен $2016 2015 (t+1) + (t+ 1) + ...+ (t+1)+ 1.$ Попробуем теперь применить критерий Эйзенштейна. Заметим, что свободный член равен $2017$ — простому числу. Осталось доказать, что остальные коэффициенты делятся на $2017.$

Заметим, что $2017 2017 y − 1= (y − 1) ,$ как многочлен над $ℤ2017,$ так как $k C2017$ для $1≤k ≤2016$ делится на $2017,$ а старший коэффициент и свободный член многочлена $2017 (y− 1)$ равны $1$ и $− 1$ соответственно. Преобразуем это равенство:

y2017− 1= (y− 1)2017

(y− 1)(y2016+ y2015+ ...+y +1)− (y− 1)2017 = 0

2016 2015 2016 (y− 1)(y + y + ...+y +1− (y− 1) )= 0

Тогда получаем, что $y2016+y2015 +...+ y+ 1− (y− 1)2016 = 0$ над $ℤ2017.$ Подставим $y = t+ 1.$ Получаем $(t+1)2016+ (t+ 1)2015 +...+ (t+1)+ 1− t2016 = 0$ Таким образом, все коэффициенты многочлена $(t+ 1)2016+ (t+ 1)2015+...+(t+1)+ 1,$ кроме старшего, делятся на $2017.$

Таким образом, для многочлена $P(t)=(t+ 1)2016+ (t+ 1)2015+...+(t+1)+ 1$ выполняется критерий Эйзенштейна, значит, он неприводим. Тогда исходный многочлен $P(x)$ тоже неприводим, так как мы использовали линейную замену $x= 3(t+ 1).$ Таким образом, $2017 2017 2016 2015 2015 2016 x − 3 = (x− 3)(x +3x + ...+ 3 x +3 )$ — искомое разложение на неприводимые.

Ответ:

$(x− 3)(x2016+ 3x2015 +...+ 32015x+ 32016)$

Ошибка.
Попробуйте повторить позже

Задача 16#76329

Даны натуральные числа $n$ и $k.$ Найдите $НОД (x2n + 1,x2k + 1).$

Показать ответ и решение

Пусть $n ≥k.$ Будем делить делить первый многочлен на второй столбиком. После подбора первого одночлена в частном мы сможем записать: $2n 2k 2n− 2k 2n−2k x +1 =(x +1)x + (−x +1).$ После подбора второго: $2n 2k 2n−2k 2n−2⋅2k 2n−2⋅2k x +1 =(x +1)(x − x )+ (x + 1).$

Возникает желание доказать по индукции, что при любом $n−k t≤ 2$ после $t$ - го шага будет равенство $2n 2k 2n−2k 2n−2⋅2k t+1 2n−t⋅2k t 2n−t⋅2k x + 1= (x + 1)(x − x + ...+ (−1) x )+((− 1) x + 1).$ База уже доказана. Если предположить, что при $t= m$ утверждение верно, то ясно что следующим одночленом в частном будет $m+2 n k (−1) (2 − (m+ 1)2 ).$ Далее нетрудно посчитать остаток и выписать нужное равенство при $t =m + 1.$

Ограничение $n−k t≤2$ введено неслучайно, ведь после $n−k 2$ - го шага мы получим в остатке $2n−2n x + 1= 2.$ То есть ненулевая константа $2$ делит нужный нам НОД. Следовательно, многочлены взаимно просты.

Ответ:

$1$

Бандлы и наборы

Комбо-тарифы сразу по нескольким предметам

Ошибка.
Попробуйте повторить позже

Задача 17#76332

Докажите, что число $7√7$ не является корнем никакого многочлена с целыми коэффициентами степени меньше $7.$

Показать доказательство

Докажем, что любой целочисленный многочлен с корнем $7√7$ делится на $x7− 7.$ Предположим противное, пусть есть целочисленный многочлен $P,$ который зануляется при $7√- x = 7$ и не делится на $7 x − 7.$

Заметим, что по критерию Эйзенштейна многочлен $7 x − 7$ неприводим над $ℤ.$ Следовательно, $7 (x − 7,P )=1.$ Тогда по теореме о линейном представлении существуют такие многочлены $A$ и $B,$ что $7 AP + B(x − 7)= 1.$ Подставим в равенство $7√- x = 7$ и получим равенство $0=1,$ противоречие. Значит, $P$ делится на $7 x − 7,$ то есть его степень не меньше $7,$ что и требовалось.

Ошибка.
Попробуйте повторить позже

Задача 18#76333

Пусть $a ,a,...,a 1 2 n$ — различные целые числа. Докажите, что многочлен

(x− a1)(x− a2)...(x− an)− 1

неприводим над $ℤ.$

Показать доказательство

Предположим, что он представим виде произведения двух целочисленных многочленов $P(x)$ и $Q (x)$ ненулевой степени. Получается, что $P (a1)Q (a1)= P(a2)Q(a2) =...=P (an)Q(an)= −1.$ Если произведение двух целых чисел равно $1,$ то одно из них равно $1,$ а другое — $− 1.$

Заметим, что $deg(P)+ deg(Q)= n.$

Если $n$ нечётно, то по принципу Дирихле степень одного из многочленов строго меньше $n 2.$ Пусть это многочлен $P.$ Он в $n$ точках принимает значения $± 1.$ Следовательно, хотя бы в $n+1 2$ из них он принимает одно и то же значение. По нашему предположению $n n+1 deg(P )< 2 < 2 ,$ значит у $P(x)$ нулевая степень, пришли к противоречию.

При чётном $n$ такой же принцип Дирихле работает во всех случаях кроме следующего: $n degP(x)= degQ(x)= 2,$ в одной половине точек $P$ равен $1,$ а $Q$ — $− 1,$ в другой — наоборот (можно поменять знаки, но для определённости рассмотрим этот случай). Заметим, что в этом случае многочлены $Q (x)+ 1$ и $P(x)− 1$ имеют одинаковый набор корней. Следовательно, они могут отличаться лишь домножением на константу. Учитывая, что многочлен $P (x)Q(x)$ унитарный и все коэффициенты $P$ и $Q$ целые, понимаем, что $P (x)− 1= Q(x)+ 1.$

Если рассмотреть другую половину ашек, то мы получим, что $P(x)+ 1= Q(x)− 1.$ Таким образом, $Q(x) =P(x)− 2= P(x)+ 2,$ пришли к противоречию.

Ошибка.
Попробуйте повторить позже

Задача 19#76334

Докажите, что если $p$ — простое число, то многочлен $f(x)= xp−1+ xp−2+ ...+ x+1$ неприводим.

Показать доказательство

Подставим $x+ 1$ вместо $x.$ Понятно, что неприводимость полученного многочлена равносильна неприводимости изначального. Раскроем в выражении $p−1 p− 2 (x+ 1) + (x +1) +...+(x+ 1)+1$ скобки и приведём подобные. С помощью формулы бинома Ньютона нетрудно убедиться, что коэффициент при $p−1−i x$ будет равен $p−1−i p−1−i p−1−i Cp− 1 + Cp−2 + ...+C p−1−i.$ С помощью последовательного применения тождества $k k− 1 k Cn−1+C n− 1 = Cn$ к цешке $p−i Cp$ получим, что $p− 1−i p−1−i p−1−i p−i Cp−1 + Cp−2 +...+Cp−1−i = Cp .$

Итак, коэффициент при $p−1−i x$ равен $p− i C p .$ Осталось заметить, что старший член не делится на $p,$ младший делится на $p,$ но не делится на $2 p.$ Остальные делятся на $p,$ потому что все цешки целые, их числитель делится на $p,$ а знаменатель — нет. Получили неприводимость по критерию Эйзенштейна.

Ошибка.
Попробуйте повторить позже

Задача 20#87099

(Лемма Гензеля). Пусть $P(x)$ многочлен с целыми коэффициентами. Тогда для любого простого $q,$ натурального $s$ и целых $r,n$ верно следующее сравнение:

s s ′ 2s P(n+ rq)≡ P(n)+ rq P (n) (mod q )

Показать доказательство

Пусть у нас есть многочлен $P (x)= a xk+ a xk−1+ ...+ ax+ a . k k−1 1 0$ Давайте теперь просто запишем наше сравнение:

sk sk−1 s ak(n +rq) + ak−1(n+ rq) + ...+ a1(n+ rq)+ a0 ≡

k k−1 s k−1 k−2 2s ≡akn + ak−1n +...+ a1n+ a0+rq (akkn + ak−1(k− 1)n + ...+ a1n +a0) (mod q )

Раскроем скобки справа и первые два слагаемых в биноме Ньютона слева:

a nk+ka nk−1rqs+ ...+ a nk−1+ a (k− 1)nk−2rqs+...+a n+ a rqs+ a ≡ k k k− 1 k−1 1 1 0

≡ aknk +ak−1nk−1+...+a1n+ a0+ rqsakknk−1+ rqsak−1(k− 1)nk−2+...+rqsa1n +rqsa0 (mod q2s)

Видно, что правая часть полностью сокращается после этого вместе с двумя первыми слагаемыми в биноме, и теперь слева остаются слагаемые, которые как раз содержат $qs$ минимум во второй степени.