Вычисления в конечных полях

1.6. фу н к ц и я и теорема Эйлера Функция Эйлера ф(т), где т - натуральное число, определяет количество взаимно простых к m числам в диапазоне от 1 до m - 1, Если число т - простое, то все натуральные числа от I до т - 1 являются взаимно простыми к т, поэтому для такого т: ip{m) = /п - 1, Для составного гп Эйлером была установлена закономерность, связанная с формулой канонического разложения числа т на со- мнохсители: где Pi, i~\,k - простые сомножители числа т ; а, - число повторе­ ний сомножителя р,- в разложении числа т . При этом любое со­ ставное число раскладывается однозначно. Приведем два варианта вычисления функции Эйлера для со­ ставных чиселт . Вариант I. Пусть в разложении числа т все сомножители разные, т.е. для V/: а, = 1, i = \,k , где к ~ число отличающихся со­ множителей. Тогда ф{т) вычисляется по следующему рекуррент­ ному выражению: Пример 1.10. Пусть т = 30. Оно раскладывается на множи­ тели 2, 3 и 5. Тогда по представленной формуле гюлучим Значит, в диапазоне от 1 до 30 находятся 8 взаимно простых чисел с 30. Вариант П. В случае, если имеются кратные сомножители, используется формула Р\ А Pi ) \ Рк / \ ф(т) = (рГ' - рГ '). 28