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

Многочлены над конечным полем

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

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

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

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

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

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

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

Задача 1#96499

Для каждого простого $p$ найдите количество неприводимых над $𝔽 p$ многочленов степени $3.$

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

Количество многочленов $P (x)∈ 𝔽[x], p$ степень которых равна $3,$ ровно

3 (p− 1)p

Это так, ведь существует ровно $p− 1$ возможных коэффициентов перед $x3$ и ровно $p$ возможных вариантов на каждый из остальных мономов. Таким образом, достаточно найти количество многочленов, приводимых над указанным полем.

Существует ровно два типа указанных многочленов:

$1)$ Многочлен раскладывается в виде произведения трех линейных многочленов. Количество таких многочленов равно(далее будем считать $3 C2$ равным нулю)

( 3 ) (p− 1) Cp + p(p− 1)+p

Поскольку существует ровно $p− 1$ коэффициент перед старшей степенью, а множество корней суть множество из трех элементов, каждый из которых лежит в $𝔽p.$

$2)$ Многочлен является суть произведением линейного многочлена, а так же многочлена второй степени, неприводимого над $𝔽p.$ Аналогично рассуждениям первого пункта, получим, что количество приводимых многочленов второй степени равно

2 ( p(p− 1) ) (p2+ p) p(p2− 1) (p− 1)(C p +p)= (p− 1)-2---+p = (p− 1) --2-- = ---2---

то есть неприводимых

2 p3−-p 2p3−-2p2-− p3+-p p3−-2p2-+p p(p−-1)2- (p− 1)p− 2 = 2 = 2 = 2

следовательно общее количество исходных многочленов равно

p2(p− 1)2 ---2----

Наконец, количество приводимых многочленов равно

( ) 2 2 (p − 1)p3− (p− 1)C3p +p(p− 1)+ p − p(p−2-1)

что после преобразований имеет вид

2 p(p−-1)(p+-1) 3

Ответ:

$p(p−-1)2(p+1) 3$

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

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

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

Задача 2#96500

Натуральные числа $a,b,c$ и простое $p >3$ таковы, что $a+ b+ c=p +1,$ и $a3+ b3+ c3− 1$ делится на $p.$ Докажите, что одно из чисел $a,b,c$ равно $1.$

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

Так как все числа $a,b,c$ меньше $p,$ достаточно доказать, что одно из них дает остаток $1$ при делении на $p.$ Рассмотрим многочлен $(x− a)(x− b)(x− c)$ по модулю $p.$ Имеем $a +b+ c≡ 1 (mod p),$ и поскольку

3 3 3 2 1 ≡a + b + c= (a+ b+c)((a+ b+c) − 3(ab+ bc+ ac))+ 3abc≡

≡1 − 3(ab+bc+ ac)+ 3abc (mod p)

числа $ab+ bc+ac$ и $abc$ также сравнимы по модулю $p:$

ab+bc+ ac≡abc≡ k (mod p)

Итак, по модулю $p$ вычеты $a,b$ и $c$ являются корнями многочлена

(x− a)(x− b)(x − c)≡ x3− x2 +kx− k≡ (x− 1)(x2 +k) (mod p)

а это и значит, что одно из них сравнимо с $1$ по модулю $p.$

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

Задача 3#96502

Пусть $f :ℤ → ℤ p p$ — произвольная функция. Тогда найдется многочлен $P(x) ∈ℤ [x] p$ степени не выше $p− 1,$ для которого при любом $c∈ 𝔽p$ выполнено $f(c)= P(c).$

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

Пусть $M f$ — множество всевозможных функций $f :ℤ → ℤ . p p$ Найдем его мощность, каждая функция однозначно определяется значениями в каждой из точек $0,1,...,p− 1,$ следовательно, $p |Mf|= p.$

Пусть $MP$ — множество многочленов $P(x)∈ℤp[x]$ степени не выше $p − 1.$ Каждый из них однозначно определяется коэффициентами перед каждым из коэффициентов некоторой из $p$ возможных степеней. Никакие два многочлена $P,Q ∈MP ,$ коэффициенты которых отличаются хотя бы в одной позиции не совпадают, поскольку их совпадение в $p$ различных точках, влечет их совпадение. И снова, $p |MP|= p .$

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

Задача 4#97180

При каких натуральных $n$ многочлен $(x+1)n+ xn+ 1$ делится на $x2+x +1?$

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

Поскольку $x+ 1≡ −x2 (mod x2 +x +1),$ получаем

n n n2n 2 2 (x+ 1) +x +1 ≡(−1) x + x + 1 (mod x +x+ 1)

Заметим, что $x3 ≡ 1 (mod x2+x +1).$

Разберем все случаи

1.: $3|n.$ Тогда $n 2n 2 n 2 (−1) x +x + 1≡ (−1) +2 (mod x + x+ 1).$ Многочлен $n (−1) +2$ на $2 x + x+1,$ конечно, не делится.
2.: $n ≡1 (mod 6).$ Тогда $n 2n 2 2 2 (− 1) x + x +1 ≡−x +x+ 1≡ 2x+ 2 (mod x +x+ 1).$
3.: $n ≡2 (mod 6).$ Тогда $n 2n 2 2 2 (− 1) x + x +1 ≡x+ x + 1≡ 0 (mod x +x +1).$
4.: $n ≡4 (mod 6).$ Тогда $(− 1)nx2n+ x2 +1 ≡x2+ x+ 1≡ 0 (mod x2 +x +1).$
5.: $n ≡5 (mod 6).$ Тогда, $(−1)nx2n+ x2+ 1≡ x2− x +1≡ 2x+ 2 (mod x2+x +1).$

Таким образом, подходят только $n≡ 2,4 (mod 6).$

Ответ:

При $n= 6k± 2$

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

Задача 5#97182

$P (x)$ и $Q(x)$ — многочлены с действительными коэффициентами. Известно, что многочлен $P(x3)+ xQ(x3)$ делится на $x3− 1.$ Докажите, что $P(x)$ и $Q (x)$ оба делятся на $x− 1.$

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

Для начала заметим, что $x3 ≡ 1 (mod x3− 1).$ Тогда получаем, что

3 P(1)+ xQ(1)≡0 (mod x − 1)

Слева линейный многочлен, поэтому такое сравнение возможно в том и только в том случае, когда $P (1)= Q(1)=0.$ Теперь заметим, что $x ≡1 (mod x− 1).$ Поэтому $P (x)≡ P(1)≡ 0 (mod x − 1).$ Аналогично $Q(x)≡ 0 (mod x− 1).$

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

Задача 6#97183

Докажите, что для любого многочлена $P(x)$ многочлен $P (P(...P(x)...))− x$ делится на $P(x)− x.$

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

Докажем тождество индукцией по числу композиций. Для одной композиции утверждение верно, поскольку тогда это утверждение о том, что $P (x)− x$ делится на $P(x)− x.$ Пусть $P◟-(P-(...P◝◜(x)...))◞−x, n$ делится на $P (x)− x.$ Тогда

P◟(P(...P◝(◜x)...))◞≡ x (mod P(x)− x) n

Тогда для $n+ 1$ композиции имеем

P◟(P(...◝P◜(x)...))◞−x≡ P(x)− x≡ 0 (mod P (x)− x) n+1

Курсы

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

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

Задача 7#97186

При каких натуральных $k$ многочлен $1+ x4 +x8+ ...+ x4k$ делится на многочлен $1+ x2 +x4+ ...+ x2k?$

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

Заметим, что при всех нечетных $k$ многочлен $P(x)= 1+x2+ x4+ ...+ x2k$ делится на многочлен $x2+1,$ а многочлен $4 8 4k Q (x)= 1+ x +x + ...+ x$ не делится на него ни при каких $k,$ поскольку при $2 x + 1= 0$ имеем $4 x = 1,$ поэтому значение $Q (x)$ будет вещественным положительным числом, а $P (x)= 0.$ Но тогда $Q(x)$ не делится на $P(x).$

Пусть теперь $k$ четно. Тогда $P (x)$ взаимно прост с многочленом $2 x + 1.$ Заметим, что $P(x)$ взаимно прост с многочленами $x ±1.$ Тогда делимость $Q(x)$ на $P(x)$ эквивалентна делимости $4 (x − 1)Q (x)$ на $2 (x − 1)P (x).$ Очевидно, выполняются равенства

(x4− 1)Q(x)= x4k+4− 1

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

Если $x2k+2− 1= 0,$ то, очевидно, и $x4k+4− 1= 0.$ Таким образом, все корни $(x2− 1)P(x)$ являются корнями $(x4− 1)Q (x),$ поэтому $(x4− 1)Q(x)$ делится на $(x2− 1)P (x),$ следовательно и $Q(x)$ делится на $P(x).$

Ответ:

При четных $k∈ ℕ$

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

Задача 8#97187

Найдите все пары натуральных чисел $x,y$ такие, что $x3+ 1$ делит $(x+ 1)y.$

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

Если $y =1,$ то задача сводится к делимости $1$ на $x2− x+ 1,$ что возможно только лишь при $x= 1.$

Пусть $y > 1.$ Введём переменную $m =y − 1$ и рассмотрим делимость $m (x+ 1)$ на $2 x − x +1.$ Заметим, что

2 2 (x +1) ≡ 3x (mod x − x+ 1)

Теперь задача сводится к рассмотрению случаев.

Если $m$ чётное, то тогда $(x+ 1)m ≡ 3m2 xm2 .$ Заметим, что $(x,x2 − x+ 1)= 1.$ Если $x= 1,$ то делимость верна при любом $m.$ Иначе $3m2$ должно делиться на $x2− x+ 1,$ то есть $x2− x+ 1$ — cтепень $3.$ Однако это выражение делится на $3$ лишь при $x ≡2 (mod 3).$ Если подставить $x =3k− 1,$ получим

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

Это может быть степенью тройки лишь при $k= 1,$ откуда $x= 2$ и $y ≥3.$

Если $m$ нечётное, то получим сравнение с $(x+ 1)xm2−1⋅3m−21.$ Опять же, если $x= 1,$ делимость верна для любого $m.$ В противном случае $3m−21(x+1)$ кратно $x2− x+ 1.$ Заметим, что $(x +1,x2− x+1)= 3.$ Значит, $x2− x+ 1$ снова должно быть степенью тройки, что возможно лишь при $x= 2.$ Отсюда получаем, что $y ≥ 2.$

Ответ:

$(x,1),x∈ ℕ,(1,y),y ∈ ℕ,(2,y),y ≥ 2$

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

Задача 9#74951

Пусть задано множество остатков от деления на 11, $A= {0,1,2,3,4,5,6,7,8,9,10}$ . Пусть над этим множеством задана степенная функция четвертой степени $($ т.е. все значения переменных и коэффициенты принадлежат только множеству $A)$

4 3 2 f(x)= x + 3x +7x + 6x+10

Найдите элемент множества $A,$ являющийся суммой корней уравнения $f(x)= 0.$

Источники: САММАТ-2022, 11.7 (см. sammat.samgtu.ru)

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

Просто переберём остатки по модулю 11:

f(0)≡ 10⁄≡ 0mod 11

f(1)≡5 ⁄≡0 mod11

f(2)≡2 ⁄≡0 mod11

f(3)≡ 0mod 11

f(4)≡ 0mod 11

f(5)⁄≡ 0mod 11

f(6)⁄≡ 0mod 11

f(7)⁄≡ 0mod 11

f(8)≡ 0mod 11

f(9)⁄≡ 0mod 11

f(10) ⁄≡0 mod11

Итак, $f(3)≡0 mod11,f(4)≡ 0mod 11,f(8)≡ 0mod 11.$

Так как многочлен степени 4, то какой-то корень кратный. Убеждаемся, что

(x4+ 3x3 +7x2+ 6x +10)= (x − 3)(x − 4)2(x− 8) mod11

Значит, сумма равна

3+4 +4+ 8≡ 8mod 11

Ответ: 8

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

Задача 10#86853

Пусть для натурального числа $n$ и простого числа $p$ нашлись натуральные числа $a ,...,a 1 n+1$ такие, что их $n$ -е степени дают одинаковые остатки при деление на $p.$ Докажите, что какие-то $ai$ и $aj$ дают одинаковые остатки при делении на $p.$

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

Рассмотрим многочлен $xn− r$ над полем $𝔽 , p$ где $r$ — остаток от деления $an 1$ на $p.$ По условию $a,...a 1 n+1$ являются его корнями. Но над нашим полем этот многочлен имеет не более $n$ корней. То есть какие-то два из чисел $a1,...,an+1$ действительно дают одинаковые остатки при делении на $p.$

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

Задача 11#86854

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

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

Заметим, что многочлен $xp− x= x(x − 1)...(x− p+1)$ над полем $𝔽 . p$ Рассмотрим многочлен $f(x)− g(x).$ По условию $0,1,...p− 1$ являются его корнями. Следовательно, $f(x)− g(x)$ делится на $x(x− 1)...(x− p +1)$ по теореме Безу, что и требовалось доказать.

Интенсивы

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

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

Задача 12#86855

Доказать, что для любого целого $m,$ не кратного $p − 1,$ существует $n,$ не кратное $p$ такое, что $nm ⁄≡ 1 (mod p).$

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

Предположим противное. То есть существует $m,$ для которого $xm ≡ 1 (mod p)$ для любого $x,$ не делящегося на $p.$ Посмотрим на многочлен $m x − 1$ над полем $𝔽p.$ Покажем, что на самом деле в таком случае $m x − 1$ делится на $p−1 x − 1.$ Заметим, что многочлен $p x − x= x(x− 1)...(x− p+ 1)$ над полем $𝔽p$ . Тогда мы понимаем, что $0,1,...p− 1$ являются корнями $m x − 1$ . Следовательно, он делится на $x(x − 1)...(x− p+1)$ по теореме Безу, то есть и на $p−1 x − 1.$ Пусть теперь $r$ — остаток от деления $m$ на $p− 1.$ Тогда многочлен $m r x − x$ делится на $p−1 x − 1,$ следовательно, и многочлен $r x − 1$ делится на $m x − 1.$ Но $r m deg(x − 1)< deg(x − 1)$ — противоречие.

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

Задача 13#86856

Назовём многочлен с целыми коэффициентами перестановочным по модулю $p,$ если его значения дают все возможные остатки при делении на $p.$ Существует ли перестановочный по модулю $101$ многочлен степени

(a) $17;$

(b) $100;$

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

(a) Подойдёт многочлен $x17.$ Предположим обратное. Пусть $a17 ≡ b17 (mod 101)$ для различных остатков $a$ и $b.$ Тогда эти остатки ненулевые. По малой теореме Ферма имеем $100 100 a ≡ b (mod 101).$ Тогда $2 17⋅6−100 17⋅6−100 2 a ≡a ≡ b ≡ b (mod 101).$ И значит $17−2⋅8 17−2⋅8 a ≡a ≡ b ≡ b (mod 101).$ Противоречие, значит многочлен $17 x$ является перестановочным.

(b) Подойдёт многочлен $100 101x + x.$ Действительно, остаток числа $100 101x +x$ при делении на $101$ равен $x.$ А многочлен $x$ является перестановочным.

(c) Подойдёт многочлен $10 101x + x.$ Действительно, остаток числа $100 101x +x$ при делении на 101 равен $x.$ А многочлен $x$ является перестановочным.

Ответ:

Существует во всех пунктах

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

Задача 14#86858

Докажите, что над полем $𝔽 p$ существует бесконечно много неприводимых многочленов. (Неприводимый многочлен — это многочлен, который нельзя представить в виде произведения двух многочленов ненулевой степени)

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

Предположим, что существует лишь конечное число неприводимых многочленов. Рассмотрим их произведение, увеличенное на $1.$ Легко видеть, что полученный многочлен не делится ни на один из неприводимых, следовательно, он сам является неприводимым — противоречие.