1 1 1 1 1 1 1 1 1 1 Рейтинг 4.61 (47 голосов)

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

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

 

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

При этом полагают, что число 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

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

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

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

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