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

Задача 1

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

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

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

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

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

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

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

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

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

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

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

Второй вопрос, сколько неприводимых? Квадратные унитарные многочлены имеют вид $x^2 + ax + b$, т.к. в $\mathbb{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$, это неприводимый в $\mathbb{Z}_2$ многочлен. Он взаимно прост с любым другим многочленом второй степени.

Задача 3

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

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

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

Задача 4

$1\cdot1=1$

$2\cdot6=1$

$3\cdot4=1$

$5\cdot9=1$

$7\cdot8=1$

$10\cdot10=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^10 = 1$

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

Задача 6

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

\[\begin{array} {|r|r|}\hline & a & b & c \\ \hline a & & & \\ \hline b & & & \\ \hline c & & & \\ \hline \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} {|r|r|}\hline & a & b & c \\ \hline a & & X & Y\\ \hline b & X & & Z\\ \hline c & Y & Z & \\ \hline \end{array}\]

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

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

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

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