Решения задач

Задача 1

Многочлен приводим, значит, представляется в виде произведения многочленов меньшей степени. Квадратный многочлен можно представть только как произведение двух многочленов первой степени: $(a x + b) (c x + d)$ . В результате должен получиться унитарный многочлен, т.е. многочлен с единичным старшим коэффициентом. Поэтому будем считать, что множители тоже унитарные.

Формально, после раскрытия скобок получится $a c x^{2} + \dots$ , значит $a c = 1$ . Вынесем множитель $a$ из первого многочлена $(a x + b) (c x + d) = (x + \frac{b}{a}) (a c x + a d) = (x + \frac{b}{a}) (x + a d) = (x + p) (x + q)$ .

Т.е. чтобы узнать, сколько приводимых многочленов, нужно понять, сколько можно составить произведений $(x + p) (x + q)$ . В $Z_{3}$ есть только три значения: {0, 1, 2}. Перечислим возможные произведения:

$(x + 0) (x + 0) = x^{2}$

$(x + 0) (x + 1) = x^{2} + x$

$(x + 0) (x + 2) = x^{2} + 2 x$

$(x + 1) (x + 1) = x^{2} + 2 x + 1$

$(x + 1) (x + 2) = x^{2} + 2$

$(x + 2) (x + 2) = x^{2} + x + 1$

В принципе, можно было не раскрывать скобки, и так понятно, что получается 6 произведений.

Ответ: 6 приводимых многочленов.

Второй вопрос, сколько неприводимых? Квадратные унитарные многочлены имеют вид $x^{2} + a x + b$ , т.к. в $Z_{3}$ есть по три варианта значений для $a$ и $b$ , всего 9 квадратных унитарных многочленов. Итого, осталось 3 неприводимых.

Ответ: 3 неприводимых многочлена.

Можете их выписать?

Задача 2

Это могут быть многочлены $x^{2}$ и $(x + 1)^{2} = x^{2} + 1$ . У них нет общего множителя, потому что они состоят из разных неприводимых множителей.

Есть ли другие ответы? Выше написаны два приводимых многочлена. Есть еще один приводимый, это $x (x + 1) = x^{2} + x$ , поэтому из квадратных многочленов остался только один $x^{2} + x + 1$ , это неприводимый в $Z_{2}$ многочлен. Он взаимно прост с любым другим многочленом второй степени.

Задача 3

Какой может быть общий делитель у таких многочленов? Он не может быть степени 2 и выше, потому что тогда на него не будет делиться $x + a$ . Т.е. общий делитель должен быть степени 1, значит, $x + a$ и должен быть общим делителем.

Если второй многочлен $x^{2} + a x + a$ делится на $x + a$ , то у него должен быть корень $- a$ . Подставим: $(- a)^{2} + a (- a) + a = a^{2} - a^{2} + a = a$ . Значит, $a = 0$ .

Ответ: $a = 0$ .

Задача 4

$1 \cdot 1 = 1$

$2 \cdot 6 = 1$

$3 \cdot 4 = 1$

$5 \cdot 9 = 1$

$7 \cdot 8 = 1$

$10 \cdot 10 = 1$

Задача 5

Можно увидеть, что по модулю 7 выполняется $2^{3} = 1$ , поэтому $2^{3} = 2^{6}$ , т.е. в множестве из шести остатков есть одинаковые, а дожно быть 6 разных остатков в приведенной системе вычетов по модулю 7.

А вот по модулю 11 образуется приведенная система вычетов:

$2^{1} = 2$

$2^{2} = 4$

$2^{3} = 8$

$2^{4} = 5$

$2^{5} = 10$

$2^{6} = 9$

$2^{7} = 7$

$2^{8} = 3$

$2^{9} = 6$

$2^{1} 0 = 1$

Это все остатки от 1 до 10. Т.е. взаимно простые с 11.

Задача 6

Бинарное отношение можно задать с помощью таблицы

\begin{array}{rr} a & b & c \\ a \\ b \\ c \end{array}

Для этого достаточно заполнить эту таблицу нулями и единицами. Соответственно, чтобы ответить на первый вопрос, сколько всего бинарных отношений, достатчно посчитать, сколькими способами можно заполнить эту таблицу нулями и единицами.

Ответ: бинарных отношений на множестве из 3 элементов $2^{9}$ .

В общем случае, если бы элементов в множестве было $n$ , то бинарных отношений было бы $2^{n^{2}}$ .

Рефлексивных отношений будет $2^{6}$ , потому что 3 из 9 клеток на главной диагонали однозначно заданы. Они все равны 1. Остается выбрать только значения для 6 оставшихся клеток.

Антирефлексивных отношений тоже $2^{6}$ , потому что в этом случае точно так же заданы значения клеток на диагонали, они все нули.

В общем случае, рефлексивных или антирефлексивных отношений будет $2^{n^{2} - n}$ , если в множестве $n$ элементов.

Чтобы посчитать симметричные отношения, нужно заметить, что для них достаточно задать только значения на диагонали матрицы (3 значения), и значения, например, под диагональю (еще 3). Это 6 значений. Значения над диагональю определяются автоматически из симметричности по значениям под диагональю.

Ответ: симметричных отношений $2^{6}$ . В общем случае их $2^{n + \frac{n^{2} - n}{2}} = 2^{\frac{n^{2} + n}{2}}$ .

Для задания антисимметричных отношений достаточно задать значения на диагонали, они могут быть произвльными, и задать значения для пар симметричных клеток:

\begin{array}{rr} a & b & c \\ a & X & Y \\ b & X & Z \\ c & Y & Z \end{array}

Оба значения $X$ не могут быть одновременно единицами. Они могут быть либо оба 0, либо 1 и 0, либо 0 и 1. Поэтому есть три варианта значений для них.

Ответ: Антисимметричных отношений: $2^{3} \cdot 3^{3}$ . В общем случае $2^{n} \cdot 3^{n + \frac{n^{2} - n}{2}}$ .

Ассиметричные отношений можно посчитать аналогично, только на диагонали не нужно выбирать значения, там они обязаны быть нулями: $3^{3}$ или $3^{n + \frac{n^{2} - n}{2}}$ в общем случае.

Количество транзитивных отношений посчитать значительно сложнее, особенно в общем случае, потому что транзитивность плохо видна по матрице. Нужно разбирать случаи. Например, все $2^{3}$ отношений, которые не имеют 1 вне главной диагонали, транзитивные. Все отношения, у которых только одна единица вне главной диагонали - тоже транзитивные. Их $2^{3} \cdot 6$ . Нужно продолжать разбирать случаи, т.ч. мы здесь не доведем эту задачу до ответа.