Таблицы Брадиса

Функция п называется функцией Эйлера.

Функция п называется функцией Эйлера.

Элементы математики в задачах - Г. А. Мерзон

Задача 14. Докажите, что порядок любого элемента конечной груп­пы О делит порядок группы О (|О|. огё а).

Указание. Для каждого элемента а группы О мы можем рассмотреть множество (а) = {ап | п е Ж}, которое обязательно будет подгруппой.

Решение. Рассмотрим подгруппу (а). Тогда ее порядок (число элемен­тов) равен в точности оМ а, поскольку а0 = е, аога а = е и ак = е ни при каком 0 < к < оМ а. Но по предыдущей задаче порядок подгруппы делит порядок группы О.

Определение 8. Обозначим через ^(п) число натуральных чисел, не превосходящих п и взаимно простых с п. Функция ^(п) называется функцией Эйлера.

Ш Другое определение функции ^(п) —число обратимых по умно­жению элементов в группе остатков Ж/пЖ.

Задача 15. Найдите: а) ^(2), ^(6), ^(30); б) ^(р); в) у(рп).

Решение. а) Эти задачи решаются прямым перебором ^(2) = 1, ^(6) = 2, ^(30) = 8.

б)  Если число р — простое, то все натуральные числа, меньшие его, взаимно просты с р. Поэтому ^(р) = р — 1.

208                                       Теория групп

в)  Натуральные числа, не превосходящие рп и имеющие с ним общий делитель, обязаны делиться на р. Поэтому их всего рп—1, включая само рп. Поэтому у(рп) = рп — рп—1.

Задача 16. Докажите, что для любых взаимно простых чисел т и п выполнено равенство у(тп) = у(т)у(п).

Решение. Выпишем все числа от 1 до тп в таблицу из т столбцов и п строк. Тогда вычеркнуть в ней все числа, имеющие с п общий делитель, очень просто: это числа, стоящие в строках, имеющих номер, не взаимно простой с п. Рассмотрим оставшиеся строки — их всего у(п). Числа, стоящие в них, имеют вид к, к + п, к + 2п, ..., к + (т — 1)п — всего т штук. Поскольку т и п взаимно просты, все эти числа дают разные остатки при делении на т. Значит, среди них (а следовательно, и в каждой строке) всего у (т) взаимно простых с т.