Приложение 1. Варианты домашних заданий

Вариант 1

1.Какова мощность множества корней уравнения x5-2x3+x=0.

2.Доказать, что множество всех счетных последовательностей натуральных чисел имеет мощность континуума.

3.Доказать, что если отношения R1 и R2 рефлексивны, то рефлексивны и отношения R1 R2, R1∩R2, R1-1, R1°R2.

4.Построить графы бинарных отношений P1, P2 и их объединния,

пересечения и произведения. Бинарные отношения заданы следующими матрицами смежности

0 1 0 1	1 0 0 1
P1 = | 1 0 0 0 |,	P2 = | 0 0 1 1 |.
| 0 0 1 1 |	| 1 0 0 1 |
1 1 1 0	1 0 1 0

5. Найти порядок перестановки

1 2 3 4 5 6 7 8 93 5 7 9 6 8 1 2 4 .

6.Найти смежные классы аддитивной группы целых чисел по подгруппе чисел, кратных натуральному числу n ( Z+ / nZ ).

7.Построить группу симметрий куба. Каков наивысший порядок циклических подгрупп, содержащихся в ней?

8.Будет ли множество Z целых чисел подгруппой аддитивной группы, подкольцом или идеалом в кольце А целых гауссовых чисел, т.е. чисел вида a + bi с целыми a и b?

9.Пусть p-простое число, p>3. Доказать, что в случае разреши-

мости сравнения x2 + x + 1 ≡ 0 (mod p) p имеет вид 6n +1. Вывести отсюда, что множество простых чисел вида 6n +1 бесконечно.

10. С помощью алгоритма Берлекэмпа разложить многочлен x6+x2+x+1 над полем F2.

155

Вариант 2

1. Пусть f(x) и ϕ(х) - два алгебраических полинома. Доказать, что множество всех корней полинома F(x)= f(x)ϕ(x) есть объединение множества всех корней полинома f(x) и множества всех корней полинома ϕ(х).

2.Какова мощность множества всех счетных последовательностей действительных чисел?

3.Доказать, что если отношения R1 и R2 иррефлексивны, то ир-

рефлексивны и отношения R1 R2, R1∩R2, R1-1. Показать, что произведение R1°R2 иррефлексивных отношений может не быть рефлексивным.

4. Построить графы бинарных отношений P1, P2 и их объединения, пересечения и произведения. Бинарные отношения заданы следующими матрицами смежности:

1 0 0 1	1 0 0 1
P1 = | 0 0 1 1 |,	P2 = | 0 1 1 0 |.
| 0 0 1 0 |	| 1 1 0 1 |
0 1 1 0	0 0 1 1

5. Найти порядок перестановки

1 2 3 4 5 6 7 8 9 103 5 4 6 7 8 9 2 1 10 .

6.Найти смежные классы аддитивной группы действительных чисел по подгруппе целых чисел ( R / Z ).

7.Построить группу симметрий октаэдра. Выделить в ней группу вращений. Совпадают ли эти группы?

8.Дано простое число p>5. Доказать, что в случае разрешмости

сравнения x4 + x3 + x2 +x +1 ≡ 0 (mod p) p имеет вид 5n +1. Вывести отсюда, что множество простых чисел вида 5n +1 бесконечно.

9. Будет ли множество B чисел x + yi, где x = y, подгруппой аддитивной группы, подкольцом или идеалом в кольце А целых гауссовых чисел, т.е. чисел вида a + bi с целыми a и b?

10.Найти поле разложения и порядок многочлена x6+x2+x+1 F2[x].

156

Вариант 3

1.Найти пересечение множества всех целых неотрицательных чисел и множества всех целых неположительных чисел.

2.Какова мощность множества всех непрерывных функций на действительной прямой?

3.Доказать, что если отношения R1 и R2 симметричны, то симметричны и отношения R1 R2, R1∩R2, R1-1, R1°R2-1.

4.Построить графы бинарных отношений P1, P2 и их объедине-

ния, пересечения и произведения. Бинарные отношения заданы следующими матрицами смежности:

0 1 0 1		1 0 0 1
P1 = | 1 0 0 0	|,	P2 = | 0 0 1 1 |.
| 0 0 1 1 |		| 1 0 0 1 |
1 1 1 0		1 0 1 0

5. Найти порядок перестановки

1 2 3 4 5 6 7 83 6 4 1 8 7 2 5 .

6. Найти смежные классы аддитивной группы комплексных чисел по подгруппе целых гауссовых чисел, т.е. чисел вида a + bi с целыми a и b.

7.Построить группу вращений октаэдра. Каков наивысший порядок циклических подгрупп, содержащихся в ней?

8.Доказать, что если сравнение x2 + 2 ≡ 0 (mod p) разрешимо, то либо p имеет вид 8n +1, либо p имеет вид 8n +3. Вывести отсюда, что множество простых чисел вида 8n + 3 бесконечно.

9.Будет ли множество С чисел x (1+ i) подгруппой аддитивной группы, подкольцом или идеалом в кольце А целых гауссовых чисел, т.е. чисел вида a + bi с целыми a и b , где x пробегает все кольцо А?

10.Дать матричное представление элементов поля F8, используя для этой цели многочлен x3+x+1, неприводимый над полем F2.

157

Вариант 4

1.Для произвольного множества Μ найти Μ и Μ∩ ?

2.Какова мощность множества всех монотонных функций на действительной прямой?

3.Доказать, что если отношения R1 и R2 антисимметричны, то

антисимметричны также отношения R1∩R 2 и R1- 1.

4. Построить графы бинарных отношений P1, P2 и их объединения, пересечения и произведения. Бинарные отношения заданы

следующими матрицами смежности:
0 1 0 1		1 0 0 1
P1 = | 1 0 1 0 |,	P2 = |	1 0 1 0 |.
| 0 1 1 1 |	|	1 0 0 1 |
0 1 0 0		0 0 1 1

5.Найти смежные классы аддитивной группы векторов плоскости (выходящих из начала координат) по подгруппе векторов, лежащих на оси абсцисс Ox.

6.Построить группу симметрий октаэдра. Каков наивысший порядок циклических подгрупп, содержащихся в ней?

7.Найдите двоичное представление четных совершенных чисел вида n=2p-1(2p - 1), где р-простое число.

8.Пусть p-простое число, p≥ 3. Доказать, что в случае разрешимости сравнения x4 + 1 ≡ 0 (mod p) число p имеет вид 8n +1. Вывести отсюда, что множество простых чисел вида 8n +1 бесконечно.

9.Будет ли множество Z[x] целочисленных многочленов подгруппой аддитивной группы, подкольцом или идеалом в кольце R[x] многочленов над полем R рациональных чисел?

10.Найти разложение многочлена x32-x на неприводимые сомножители в кольце F2[x].

158

Вариант 5

1.Каково должно быть разбиение конечного множества Μ на

два непустых класса Μ=Μ1Μ2, чтобы декартово произведение Μ1×Μ2 имело наибольшее число элементов?

2.Доказать, что не существует множества, содержащего все множества.

3.Построить бинарное отношение рефлексивное, симметричное

ине транзитивное.

4.Построить графы бинарных отношений P1, P2 и их объединения, пересечения и произведения. Бинарные отношения заданы следующими матрицами смежности:

1 1 0 1	1 0 0 1
P1 = | 1 0 1 0 |,	P2 = | 0 1 1 1 |.
| 0 0 1 1 |	| 0 0 0 1 |
1 1 1 0	1 0 1 0

5.Найти смежные классы аддитивной группы векторов плоскости (выходящих из начала координат) по подгруппе векторов, лежащих на оси ординат Oу.

6.Описать группу всех симметрий прямой призмы, в основании которой лежит правильный 6-угольник. Выделить в ней группу вращений. Совпадают ли эти группы?

7.Доказать бесконечность числа простых чисел вида 4m+1.

8.Найти все простые числа p≥ 3, для которых разрешимо сравнение x2 + 2x - 2 ≡ 0 (mod p). Доказать, что в прогрессии 12n-1 содержится бесконечно много простых чисел.

9.Будет ли множество I многочленов, не содержащих членов с xk для всех k<n (где n>1) подгруппой аддитивной группы подкольцом или идеалом в кольце Z[x] целочисленных многочленов?

10.Дать матричное представление элементов поля F8, используя для этой цели многочлен x3+ x2+1, неприводимый над полем F2.

159

Вариант 6

1.Доказать, что ≠ { }.

2.Доказать, что множества всех точек квадрата и отрезка эквивалентны.

3.Построить бинарное отношение рефлексивное, антисимметричное и не транзитивное.

4.Построить графы бинарных отношений P1, P2 и их объединения, пересечения и произведения. Бинарные отношения заданы следующими матрицами смежности:

0 1 0 1	1 1 0 1
P1 = | 1 0 1 1 |,	P2 = | 1 0 1 0 |.
| 0 0 1 1 |	| 1 0 1 1 |
1 1 0 0	0 1 1 1

5.Какой наивысший порядок могут иметь перестановки на множестве из 12 элементов?

6.Найти смежные классы мультипликативной группы комплексных чисел, отличных от нуля, по подгруппе чисел, равных по модулю единице.

7.Описать группу всех симметрий прямой призмы, в основании которой лежит правильный пятиугольник.

8. Найти решения сравнения

x30 ≡ 14 (mod 67).

9.Будет ли множество I многочленов с четными старшими коэффициентами подгруппой аддитивной группы, подкольцом или идеалом в кольце Z[x] целочисленных многочленов?

10.Найти разложение многочлена x27-x на неприводимые сомножители в кольце F3[x].

160

Вариант 7

1.Доказать, что существует лишь одно множество, не имеющее элементов.

2.Доказать, что множества точек куба и отрезка эквивалент-

ны.

3.Построить бинарное отношение рефлексивное, не симметричное и транзитивное.

4.Построить графы бинарных отношений P1, P2 и их объединния, пересечения и произведения. Бинарные отношения заданы следующими матрицами смежности:

0 0 0 1	1 0 0 1
P1 = | 1 0 1 0 |,	P2 = | 0 0 1 1 |.
| 0 1 1 1 |	| 1 0 0 1 |
0 0 1 0	1 0 1 0

5.Найти смежные классы мультипликативной группы комплексных чисел, отличных от нуля, по подгруппе положительных действительных чисел.

6.Описать группу всех симметрий прямой призмы, в основании которой лежит правильный десятиугольник. Выделить в ней группу вращений. Совпадают ли эти группы?

7.Найти все пифагоровы треугольники с целочисленными длинами сторон, у которых длина гипотенузы не превосходит 20.

8. Найти решения сравнения 23x5 ≡ 15 (mod 73).

9. Будет ли множество I многочленов с четными свободными членами подгруппой аддитивной группы, подкольцом или идеалом в кольце Z[x] целочисленных многочленов?

10.Найти пять наименьших простых чисел р, таких, что многочлен xр-1+xр-2+xр-3+…+x2+x+1 неприводим над полем F2.

161

Вариант 8

1.Существуют ли такие множества А, В и С, что А∩В≠,

А∩С= , (А∩В)\С= ?

2.Установить биективное соответствие между точками квадрата

иплоскости.

3.Построить бинарное отношение не рефлексивное, антисимметричное и транзитивное.

4.Построить графы бинарных отношений P1, P2 и их объединения, пересечения и произведения. Бинарные отношения заданы следующими матрицами смежности:

1 0 0 1		1 0 0 1
P1 = |	0 0 1 1 |,	P2 = | 0 1 1 0 |.
| 0 0 1 0 |		| 1 1 0 1 |
	0 1 1 0	0 0 1 1

5.Представить в виде произведений независимых циклов следующее произведение транспозиций (0 1)(1 2)(2 3)(3 4)(4 5).

6.Найти смежные классы мультипликативной группы комплексных чисел, отличных от нуля, по подгруппе действительных чисел.

7.Описать группу всех симметрий прямой призмы, в основании которой лежит правильный n-угольник. Выделить в ней группу вращений. Совпадают ли эти группы?

8. Найти решения сравнения

37x6 ≡ 69 (mod 73).

9.Доказать, что факторкольцо кольца D[x] многочленов с дейст-

вительными коэффициентами по идеалу многочленов, делящихся на x2 + 1, изоморфно полю комплексных чисел a + bi с известными операциями сложения и умножения.

10.С помощью алгоритма Берлекэмпа разложить многочлен x7+x6+x5+2x3+x2+2x+2 над полем F3.

162

Вариант 9

1.Доказать, что А В= А=В, где - операция симметрической разности.

2.Какова мощность множества всех иррациональных чисел?

3.Доказать, что пересечение любой системы эквивалентностей на множестве А есть эквивалентность на А.

4.Построить графы бинарных отношений P1, P2 и их объединения, пересечения и произведения. Бинарные отношения заданы следующими матрицами смежности:

0 1 0 1	1 0 0 1
P1 = | 1 1 0 0 |,	P2 = | 1 0 1 1 |.
| 0 0 1 1 |	| 1 1 0 1 |
1 0 1 0	1 0 1 0

5. Представить в виде произведений независимых циклов следующее произведение транспозиций (0 2)(3 6)(2 6)(0 3).

6.Найти смежные классы симметрической группы Sn по подгруппе подстановок, оставляющих число n на месте.

7.Описать группу всех симметрий правильной пирамиды, в основании которой лежит правильный семиугольник. Выделить в ней группу вращений. Совпадают ли эти группы?

8. Найти решения сравнения

44 x21 ≡ 53 (mod 73).

9.Пусть А - кольцо целых гауссовых чисел вида a + bi с целыми a и b, I - множество всех чисел a + bi с четными a и b. Доказать, что I является идеалом в А.

10.Найти порядок многочлена x7+2x6+x4+2x2+x над полем F3.

163

Вариант 10

1.Доказать, что А∩В= А В= А В, где - операция симметрической разности.

2.Доказать существование трансцендентных (неалгебраических) чисел.

3.Доказать, что объединение R1 R2 эквивалентностей R1 и R2 является эквивалентностью R1 R2 = R1°R2.

4.Построить графы бинарных отношений P1, P2 и их объединения, пересечения и произведения. Бинарные отношения заданы следующими матрицами смежности:

0 1 1 1	1 0 1 1
P1 = | 0 0 1 0 |,	P2 = | 1 1 1 0 |.
| 0 1 1 0 |	| 1 0 0 1 |
1 1 0 0	0 0 0 1

5.Найти все гомоморфные отображения циклической группы {a} порядка n в себя.

6.Описать группу всех симметрий правильной пирамиды, в основании которой лежит правильный n-угольник.

7.Пусть К - целое положительное число. Доказать, что в ряде натуральных чисел имеется бесчисленное множество последова-

тель-ностей М, М+1, … , М+К-1, не содержащих простых чисел. 8. Найти решения сравнения x7 ≡ 37 (mod 101).

9.Найти смежные классы А по I, где А - кольцо целых гауссовых чисел вида a+bi с целыми a и b, а I - множество всех чисел вида a+bi с четными a и b.

10.Найти поле разложения для многочлена x6+2x4+2x2+2x-1 над полем F3.

164

Вариант 11

1.Доказать, что А В=С В С = А С А = В, где - операция симметрической разности.

2.Доказать, что всякое бесконечное подмножество счетного множества счетно.

3.Доказать, что произведение R1°R2 эквивалентностей R1 и R2 является эквивалентностью R1°R2 = R2°R1.

4.Построить графы бинарных отношений P1, P2 и их объединения, пересечения и произведения. Бинарные отношения заданы следующими матрицами смежности:

1 1 0 1	1 0 0 1
P1 = | 1 0 1 0 |	P2 = | 0 1 1 1 |
| 0 0 1 1 |	| 0 0 0 1 |
0 1 1 0	1 0 1 1

5.Доказать, что всякая перестановка σ S n может быть представлена как произведение транспозиций вида (1 2), (1 3), …, (1 n).

6.Найти все гомоморфные отображения циклической группы {a} порядка 6 в циклическую группу {b} порядка 18.

7.Описать группу всех симметрий правильной пирамиды, в основании которой лежит правильный десятиугольник. Выделить в ней группу вращений. Совпадают ли эти группы?

8.Найти решения сравнения x5 ≡ 44 (mod 101).

9.Пусть А - кольцо целых гауссовых чисел вида a + bi с целыми a и b), I - множество всех чисел a + bi с четными a и b. В факторкольце А / I найти делители нуля и этим показать, что А / I не является полем.

10. Найти разложение многочлена x64-x на неприводимые сомножители в кольце F2[x].

165

Вариант 12

1.Для множеств определить операции и \ через операции и ∩, где - операция симметрической разности.

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

3.Доказать, что множество всех подмножеств данного множест-

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

4. Построить графы бинарных отношений P1, P2 и их объединения, пересечения и произведения. Бинарные отношения заданы следующими матрицами смежности:

0 1 0 1	1 0 0 1
P1 = | 1 0 0 0 |,	P2 = | 1 0 1 0 |.
| 0 0 1 1 |	| 1 0 1 1 |
1 1 0 1	0 1 1 0

5.Доказать, что всякая перестановка σSn может быть представлена как произведение транспозиций вида (1 2), (2 3), … , (n-1 n).

6.Найти все гомоморфные отображения циклической группы {a} порядка 18 в циклическую группу {b} порядка 6.

7.Описать группу всех симметрий правильной пирамиды, в основании которой лежит правильный 9-угольник. Выделить в ней группу вращений. Совпадают ли эти группы?

8.Найти решения сравнения x3 ≡ 23 (mod 109).

9.Доказать, что фактор-кольцо А / I кольца целых гауссовых чисел (т.е. чисел вида a + bi с целыми a и b) по главному идеалу I=(3) есть поле из девяти элементов.

10.Дать матричное представление элементов поля F16, используя для этой цели многочлен x4+x+1, неприводимый над полем F2.

166

Вариант 13

1.Для множеств определить операции ∩ и \ через операции и, где - операция симметрической разности.

2.Доказать, что множество бесконечно оно эквивалентно некоторому собственному подмножеству.

3.Доказать, что всякое частично упорядоченное множество содержит не более одного наибольшего (наименьшего) элемента.

4.Построить графы бинарных отношений P1, P2 и их объединения, пересечения и произведения. Бинарные отношения заданы следующими матрицами смежности:

0 0 0 1	1 1 0 1
P1 = | 1 0 1 0 |,	P2 = | 0 0 1 0 |.
| 1 0 1 1 |	| 1 0 0 1 |
0 1 1 0	0 0 1 0

5.Доказать, что всякая перестановка σ Sn может быть представлена как произведение циклов (1 2) и (1 2 3 … n).

6.Найти все гомоморфные отображения циклической группы {a} порядка 12 в циклическую группу {b} порядка 15.

7.Построить группу симметрий тетраэдра. Выделить в ней группу вращений. Совпадают ли эти группы?

8.Среди вычетов приведенной системы по модулю 37 указать первообразные корни и вычеты степени 15.

9.Доказать, что фактор-кольцо А / I кольца целых гауссовых чисел (т.е. чисел вида a + bi с целыми a и b) по главному идеалу I=(n) тогда и только тогда будет полем, когда n - есть простое число, не равное сумме двух квадратов целых чисел.

10.Найти разложение многочлена x25-x на неприводимые сомножители в кольце F5[x].

167

Вариант 14

1.Для множеств определить операции и ∩ через операции \ и, где - операция симметрической разности.

2.Доказать, что множество всех конечных подмножеств счетного множества счетно.

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

4.Построить графы бинарных отношений P1, P2 и их объединения, пересечения и произведения. Бинарные отношения заданы следующими матрицами смежности:

1 0 0 1	1 0 0 1
P1 = | 0 0 1 1 |,	P2 = | 0 1 1 1 |.
| 1 0 1 0 |	| 1 1 0 1 |
0 1 1 0	0 0 1 1

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

6.Найти все гомоморфные отображения циклической группы {a} порядка 6 в циклическую группу {b} порядка 25.

7.Каков наивысший порядок циклических подгрупп, содержащихся в группе вращений тетраэдра? Построить их.

8.Среди вычетов приведенной системы по модулю 43 указать первообразные корни и вычеты степени 6.

9.Пусть (n) - идеал, порожденный целым числом n>1 в кольце Z[x] целочисленных многочленов. Доказать, что фактор-кольцо

Z[x]/(n) изоморфно кольцу Zn[x] многочленов над кольцом вычетов по модулю n.

10.Пусть θF32 - корень неприводимого многочлена x5+x+1 F2[x]. Найти минимальный многочлен элемента β=1+θ2 над полем F2.

168

Вариант 15

1.Доказать, что для множеств нельзя определить операцию \ через операции ∩ и .

2.Доказать, что множество многочленов от одной переменной с целыми коэффициентами счетно.

3.Построить пример частично упорядоченного множества, имеющего точно один минимальный элемент, но не имеющего наименьшего элемента.

4.Построить графы бинарных отношений P1, P2 и их объединения, пересечения и произведения. Бинарные отношения заданы следующими матрицами смежности:

0 1 0 1	1 0 0 1
P1 = | 1 0 0 0 |,	P2 = | 0 0 1 1 |.
| 0 0 1 1 |	| 1 0 0 1 |
1 1 1 0	1 0 1 0

5.Доказать, что всякая четная перестановка может быть представлена как произведение циклов вида (1 2 3), (1 2 4), … , (1 2 n).

6.Найти факторгруппу аддитивной группы целых чисел по подгруппе чисел, кратных данному натуральному числу n.

7.Каков наивысший порядок циклических подгрупп, содержащихся в группе симметрий тетраэдра? Построить их.

8.Среди вычетов приведенной системы по модулю 61 указать первообразные корни и вычеты степени 10.

9.Доказать, что любая конечная подгруппа мультипликативной группы F* произвольного поля F циклична.

10.Найти порядок многочлена x11-x8+x4-x2+1 над полем F2.

169

Вариант 16

1.Доказать, что для множеств нельзя определить операцию через операции ∩ и \.

2.Доказать, что множество всех полиномов с рациональными коэффициентами счетно.

3.Доказать, что если отношение R - частичный порядок, то отношение R-1 также является частичным порядком.

4.Построить графы бинарных отношений P1, P2 и их объединения, пересечения и произведения. Бинарные отношения заданы следующими матрицами смежности:

0 1 0 1	1 0 0 1
P1 = | 1 0 1 0 |,	P2 = | 1 0 1 0 |.
| 0 1 1 1 |	| 1 0 0 1 |
0 1 0 0	0 0 1 1

5. Разложить на независимые циклы перестановку

0 1 2 3 4 5 6 7 8 94 2 1 0 3 5 9 8 6 7 .

6.Найти факторгруппу аддитивной группы целых чисел, кратных 3, по подгруппе чисел, кратных 15.

7.Построить группу симметрий куба. Выделить в ней группу вращений. Совпадают ли эти группы?

8.Найти число решений сравнения x60 ≡ 79 (mod 97).

9.Пусть F - поле. Доказать, что если его мультипликативная группа F* циклична, то F - конечное поле.

10.Разложить многочлен x6+x5+x4+x2+x+1 с помощью алгоритма Берлекэмпа над полем F2.

170

Вариант 17

1.Доказать, что множество из n элементов имеет 2n подмножеств.

2.Доказать, что множество всех матриц с рациональными элементами счетно.

3.Доказать, что любое непустое конечное частично упорядоченное множество содержит минимальный и максимальный элементы.

4.Построить графы бинарных отношений P1, P2 и их объединения, пересечения и произведения. Бинарные отношения заданы следующими матрицами смежности:

1 1 0 1	1 0 0 1
P1 = | 1 0 1 0 |,	P2 = | 0 1 1 1 |.
| 0 0 1 1 |	| 0 0 1 1 |
1 0 1 0	1 0 1 0

5. Разложить на независимые циклы перестановку

0 1 2 3 4 5 6 7 8 93 9 8 5 4 6 0 1 2 7 .

6.Найти факторгруппу аддитивной группы целых чисел, кратных 4, по подгруппе чисел, кратных 24.

7.Каков наивысший порядок циклических подгрупп, содержащихся в группе вращений куба? Построить их.

8.Найти число решений сравнения x55 ≡ 17 (mod 97).

9.Показать, что каждый элемент конечного поля Fq характеристики р имеет в этом поле один и только один корень р-й степени.

10.Найти разложение многочлена x49-x на неприводимые сомножители в кольце F7[x].

171

Вариант 18

1.Решить систему уравнений

А ∩ Х = В,

А Х = С, где А, В, и С - данные множества и В А С.

2.Доказать, что множество всех алгебраических чисел счетно.

3.Построить отношение линейного порядка на множестве N 2.

4.Построить графы бинарных отношений P1, P2 и их объединения, пересечения и произведения. Бинарные отношения заданы следующими матрицами смежности:

1 1 0 1	1 1 0 1
P1 = | 1 0 1 1 |,	P2 = | 1 0 1 0 |.
| 0 0 1 1 |	| 1 0 1 1 |
1 1 0 0	1 1 0 0

5. Разложить на независимые циклы перестановку

1 2 3 4 5 6 7 8 92 1 6 7 4 8 5 9 3 .

6.Найти факторгруппу мультипликативной группы действительных чисел, отличных от нуля, по подгруппе положительных чисел.

7.Каков наивысший порядок циклических подгрупп, содержащихся в группе симметрий куба? Построить их.

8.Делится ли число 21093-2 на 10932 ?

9.Доказать, что для f Fq[x] справедливо равенство [f(x)]q = f(xq).

10.Разложить многочлен x8+x7+x5+x4+x3+x+1 с помощью алгоритма Берлекэмпа над полем F2.

172

Вариант 19

1.Решить систему уравнений

А\Х=В,

Х\А=С, где А, В, и С - данные множества и В А, А∩С= .

2.Доказать, что множество всех вещественных чисел несчетно.

3.Построить отношение линейного порядка на множестве N 3.

4.Построить графы бинарных отношений P1, P2 и их объединения, пересечения и произведения. Бинарные отношения заданы следующими матрицами смежности:

0 0 0 1	1 0 0 1
P1 = | 1 0 1 0 |,	P2 = | 0 0 1 1 |.
| 0 1 1 1 |	| 1 0 0 1 |
0 0 1 0	1 0 1 0

5. Разложить на независимые циклы перестановку

α β γ δ ε ζ ζ δ β γ α ε.

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

7.Построить группу симметрий октаэдра. Выделить в ней группу вращений. Совпадают ли эти группы?

8.Решить сравнение 256х ≡ 179 (mod 337).

9.Показать, что любой квадратный многочлен из Fq[x] разлагается над полем Fq2 на линейные множители.

10.Найти круговые многочлены Q15 и Q32.

173

Вариант 20

1.Решить систему уравнений

А\Х=В,

А Х=С, где А, В и С - данные множества и В А С.

2.Доказать, что множество всех трансцендентных (неалгебраических) чисел несчетно.

3.Построить отношение линейного порядка на множестве C комплексных чисел.

4.Построить графы бинарных отношений P1,P2 и их объединения, пересечения и произведения. Бинарные отношения заданы слдующими матрицами смежности:

1 0 0 1	1 0 0 1
P1 = | 0 1 1 1 |,	P2 = | 0 1 1 0 |.
| 0 0 1 0 |	| 1 1 0 1 |
1 1 1 0	0 0 1 1

5. Разложить на транспозиции перестановку

0 1 2 3 4 5 6 7 8 93 5 7 1 0 4 8 9 2 6 .

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

7.Каков наивысший порядок циклических подгрупп, содержащихся в группе вращений октаэдра? Построить их.

8.Решить сравнение 1215х ≡ 560 (mod 2755).

9.Пусть Fq - конечное поле характеристики р. Доказать, что для

многочлена f Fq[x] f′(x)=0 тогда и только тогда, когда f является р-й степенью некоторого многочлена из Fq[x].

10. Дать матричное представление элементов поля F16, используя для этой цели многочлен x4+x3+1, неприводимый над полем F2.

174

Вариант 21

1.Доказать, что А = В ( А\ В) ( В \ А) = .

2.Пусть заданы множества Χ={a,b,c,d,e} и Υ={α,β,χ,δ}. Найти число сюръективных отображений множества Χ на множество Υ.

3.Доказать, что любое конечное множество можно линейно упорядочить.

4.Построить графы бинарных отношений P1, P2 и их объединения, пересечения и произведения. Бинарные отношения заданы следующими матрицами смежности:

0 1 0 1	1 0 0 1
P1 = | 1 1 0 0 |,	P2 = | 0 0 1 1 |.
| 0 0 1 1 |	| 1 1 0 1 |
1 0 1 1	1 0 1 0

5. Разложить на транспозиции перестановку

1 2 3 4 5 6 73 6 1 7 2 5 4 .

6.Доказать, что для мультипликативной группы вещественных невырожденных квадратных матриц порядка n ее фактор-группа по подгруппе матриц с положительными определителями является циклической группой второго порядка.

7.Группа вращений куба естественным способом определяет группу перестановок на множестве его ребер. Построить эту группу и определить типы всех перестановок из этой группы.

8.Решить сравнение 1296х ≡ 1105 (mod 2413).

9.Пусть К - произвольное поле и n - натуральное число, большее

единицы. Доказать, что многочлен хn-1 + хn-2 + … + х +1 неприводим над К, только в случае, когда n - простое число.

10. Найти порядок многочлена x9+x6+x4+x2+1 над полем F2.

175

Вариант 22

1.Доказать, что любое множество есть объединение всех своих подмножеств.

2.Пусть для множества Х его мощность равна n. Найти число всех подмножеств в Х, состоящих из четного числа элементов.

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

4.Построить графы бинарных отношений P1, P2 и их объединения, пересечения и произведения. Бинарные отношения заданы следующими матрицами смежности

0 1 1 1	0 0 1 1
P1 = | 1 0 1 0 |,	P2 = | 1 1 1 0 |.
| 0 1 1 0 |	| 1 0 0 1 |
1 1 0 0	0 0 0 1

5. Определить четность перестановки

1 2 3 4 5 6 75 6 4 7 2 1 3 .

6.Доказать, что для мультипликативной группы комплексных невырожденных квадратных матриц порядка n ее фактор-группа по подгруппе матриц с определителями, по модулю равными единице, изоморфна мультипликативной группе положительных чисел.

7.Группа вращений тетраэдра естественным способом определяет группу перестановок на множестве его ребер. Построить эту группу и определить типы всех перестановок из этой группы.

8.Найти все целые решения x и y уравнения 47x - 111y = 89.

9.Найти наименьшее простое число р, такое, что многочлен

х22+х21+ … +х+1 неприводим над полем Fр.

10. Дать матричное представление элементов поля F32, используя для этой цели многочлен x5+x+1, неприводимый над полем F2.

176

Вариант 23

1.Доказать, что любое множество есть объединение всех своих конечных подмножеств.

2.Пусть для множества Х его мощность равна n. Найти число всех подмножеств в Х, состоящих из нечетного числа элементов.

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

4.Построить графы бинарных отношений P1, P2 и их объединения, пересечения и произведения. Бинарные отношения заданы следующими матрицами смежности:

1 1 0 1	1 0 0 1
P1 = | 1 0 1 0 |,	P2 = | 0 1 1 1 |.
| 0 0 1 0 |	| 1 1 0 1 |
0 1 1 0	1 0 1 1

5. Определить четность перестановки

1 2 3 4 5 6 7 83 5 2 1 6 4 8 7 .

6.Доказать, что для мультипликативной группы комплексных невырожденных квадратных матриц порядка n ее фактор-группа по подгруппе матриц с положительными определителями изоморфна мультипликативной группе комплексных чисел, по модулю равных единице.

7.Группа вращений октаэдра естественным способом определяет группу перестановок на множестве его ребер. Построить эту группу и определить типы всех перестановок из этой группы.

8.Найти решение сравнения x21 ≡ 5 (mod 71).

9.Найти порядок многочлена x5+x4+x2+x+1над полем F2.

10.Найти разложение многочлена x16-x на неприводимые сомножители в кольце F4[x].

177

Вариант 24

1.Доказать, что любое множество есть объединение всех своих одноэлементных подмножеств.

2.Будет ли сюръекцией отображение ϕ:S→L из множества S слов русского языка в множество L букв русского алфавита, которое каждому слову ставит в соответствие его первую букву?

3.Доказать, что множество из n элементов можно линейно упо-

рядочить n! способами.

4. Построить графы бинарных отношений P1, P2 и их объединения, пересечения и произведения. Бинарные отношения заданы следующими матрицами смежности:

0 0 1 1	1 0 0 1
P1 = | 1 1 0 0 |,	P2 = | 1 0 1 0 |.
| 0 0 1 1 |	| 0 0 1 1 |
1 1 0 1	0 1 1 1

5.Определить четность перестановки

3 5 6 4 2 1 72 4 1 7 6 5 3 .

6.Пусть G - группа всех движений трехмерного пространства, H– подгруппа параллельных переносов, K - подгруппа вращений вокруг данной точки O. Доказать, что H является нормальным делителем группы G, а K - нет.

7.Группа вращений октаэдра естественным способом определяет группу перестановок на множестве его граней. Построить эту группу и определить типы всех перестановок из этой группы.

8.Найти решение для системы cравнений

x≡ 3 (mod 8), x ≡ 1 (mod 15), x ≡ 11 (mod 20).

9.Найти решения сравнения x35 ≡ 17 (mod 67).

10. Пусть ζ - корень n-й степени из единицы над полем К. Доказать, что

0 при ζ ≠ 1;

1+ζ+ζ2+…+ζn-1 = n при ζ = 1.

178

Вариант 25

1.Имеется последовательность множеств Х0 Х1 Х2…Хn…. Доказать, что пересечение любой бесконечной подпоследовательности этих множеств совпадает с пересечением всей последовательности.

2.Доказать, что множество всех рациональных чисел счетно.

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

4.Построить графы бинарных отношений P1, P2 и их объединения, пересечения и произведения. Бинарные отношения заданы следующими матрицами смежности:

1 1 0 1	1 0 0 1
P1 = | 1 0 1 0 |,	P2 = | 0 1 0 0 |.
| 0 1 1 1 |	| 1 1 0 1 |
0 1 1 0	1 0 1 1

5. Определить четность перестановки

2 7 5 4 8 3 6 13 5 8 7 2 6 1 4 .

6.Пусть G - группа всех движений трехмерного пространства, H - подгруппа параллельных переносов, K - подгруппа вращений вокруг данной точки O. Доказать, что K не является нормальным делителем группы G.

7.Группа вращений тетраэдра естественным способом определяет группу перестановок на множестве его граней. Построить эту группу и определить типы всех перестановок из этой группы.

8.Найти общее решение для системы cравнений

x ≡ 1	(mod 3), x ≡ 4 (mod 5), x ≡ 2 (mod 7),
x ≡ 9	(mod 11), x ≡ 3 (mod 13).

9.Решить сравнение 9x2+29x+62≡0(mod 64).

10.Пусть θF64 - корень неприводимого многочлена x6+x+1 F2[x]. Найти минимальный многочлен элемента β=1+θ2 над полем F2.

179

Вариант 26

1.Имеется последовательность множеств Х0 Х1 Х2…Хn…. Доказать, что объединение любой бесконечной подпоследовательности этих множеств совпадает с объединением всей последовательности.

2.Доказать, что если множество X бесконечно, а его подмноже-

ство Y конечно, то существует биективное отображение X\Y→X.

3.Доказать, что всякое конечное линейно упорядоченное множество вполне упорядочено.

4.Построить графы бинарных отношений P1, P2 и их объединения, пересечения и произведения. Бинарные отношения заданы следующими матрицами смежности:

0 0 0 1	1 0 0 1
P1 = | 1 0 1 0 |,	P2 = | 0 0 1 0 |.
| 0 0 1 1 |	| 1 0 0 1 |
0 1 1 0	0 0 1 0

5. Определить четность перестановки

1 2 3 … … … … n-1 n

2 4 6 … 1 3 5 … … … .

6.Пусть G - группа всех движений трехмерного пространства, H – подгруппа параллельных переносов, K - подгруппа вращений вокруг данной точки O. Доказать, что факторгруппа G / H изоморфна K.

7.Группа вращений куба естественным способом определяет группу перестановок на множестве его граней. Построить эту группу и определить типы всех перестановок из этой группы.

8.Решить систему сравнений

3x+4y-29≡0(mod 143), 2x-9y+84 ≡0(mod 143).

9.Решить сравнение x3+2x+2≡0(mod 125).

10.Дать матричное представление элементов поля F16, используя для этой цели многочлен x4+x+1, неприводимый над полем F2.

180