Расчет значения функции Эйлера

Целое положительное число

Функция Эйлера для заданного числа равна

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

При этом полагают, что число 1 взаимно просто со всеми натуральными числами.

Если заданное число N является простым то логично предложить что функция Эйлера будет равна N-1, так как все числа меньше N, являются взаимно простыми к заданному.

Например, значение функции Эйлера числа 33 равно 20. Как такое получилось?

Разложим 33 на множители получим 3*11. Запомним их и будем сравнивать с рядом чисел от 1 до 32.

Напомним, что взаимно простыми числами являются таки числа, которые не имеют общих делителей.

Считаем взаимно простые числа: 1,2 ,3(не учитывем),4,5,6(делится на 3),7,8,9,10,11(делится на 11),12,13,14,15,16,17,18,19,20,21(делится на три),22(делится на 11),23,24,25,26,27,28,29,30,31,32

Посчитаем сколько получилось зачеркнутых чисел?

Их 12, ряд чисел содержит 32 элемента ( от 1 до 33) тогда количество незачеркнтуых (взаимно простых) чисел будет 32-12 =20

Есть еще простой способ рассчитывать значения функции

Разложим произвольное число например 4832 на простые множители.

Получим $Простые множители заданного числа$

Функция Эйлера равна $(2^{5}-2^{4})*(151^{1}-151^{0}=(32-16)(151-1)=2400$

То есть, если у вас число N представлено в виде простых сомножителей вида $P_1^{B_1}P_2^{B_2}.....P_m^{B_m}$

то функция Эйлера будет равна

$(P_1^{B_1}-P_1^{B_1-1})(P_2^{B_2}-P_2^{B_2-1}).....(P_m^{B_m}-P_m^{B_m-1})$

Вот еще пример

Рассчитаем значение фунции числа 100

$Простые множители заданного числа$

тогда значение функции Эйлера равно $функция эйлера$

Применимость числа Эйлера в теории чисел и криптографии достаточно велико, но мы будем её использовать для расчета линейных диофантовых уравнений с двумя неизвестными.

Удачных расчетов!