Общая схема решения (по крайней мере, одна из возможных) задачи 4.4.2 (про группу
).
1. Исследовать, как на произвольную матрицу действует ее умножение на матрицы
,
и их степени.
2. Заметить, что если элементы какого-либо одного столбца матрицы из
оба не нулевые, то они взаимно просты (то же справедливо и для строк).
3. Выбрать какой-либо столбец или строку. Пусть, для определенности, это будет первый столбец. Рассмотреть матрицы, у которых оба элемента в первом столбце не нулевые.
4. Используя результаты пункта 1, реализовать алгоритм Евклида для элементов первого столбца. Матрица приводится к виду, в котором первый столбец равен либо
, либо
.
5. Снова используя результаты пункта 1, привести полученную матрицу к единичной. Здесь же уместно будет рассмотреть остальные матрицы из
, у которых есть нуль в первом столбце - они приводятся к единичной почти так же, как матрицы полученные на выходе пункта 4.
6. Осталось только вспомнить, что мы на всем протяжении использовали умножение на матрицы
и
, и что обратные к ним являются их же степенями. И задача решена!
Я понимаю, что автор топика уже давно решил эту задачу, но думаю что данная схема решения будет полезна другим, кто затрял с решением и ищет помощи.