Эйлер, один из самых занятых людей в истории математики, впервые продемонстрировал эту функцию в 1763 году. Он попытался использовать pi ( π) для обозначения функции, но оказалось, что число pi было занято. В 1801 году Гаусс предложил вместо этого использовать фи ( ). В 1879 году Джеймс Джозеф Сильвестр назвал ее «Totient Function».

Определившись с именем и обозначениями, давайте посмотрим, что он делает. Взаимопростая пара — это такой, в котором наибольший общий делитель двух чисел равен 1. У них нет более крупных общих делителей; они относительно просты.

Функция Totient сообщает нам, сколько взаимно простых чисел имеет наименьшее, чем оно, число. Меньшие взаимно простые числа числа 9 — это 1, 2, 4, 5, 7 и 8. (9) = 6. Но как это сделать?

В поисках Тотиента

Для простых чисел

Для простых чисел значение Totient 1меньше самого себя. Каждое число, меньшее простого числа, относительно простое с ним. Это определение простого числа. Итак, для любого простого pчисла (p) = p -1. Это было достаточно просто.

Для основных сил

Для простого числа, pвозведенного в степень k, единственными числами, меньшими pᵏкоторых НЕ являются его взаимно простые числа, являются другие числа, кратные p. Это потому , что pэто единственный фактор в pᵏ.

Все pᵏмножители могут быть представлены: p, 2p, 3p, ..., pᵏ⁻¹p.

pᵏ⁻¹обязательно является наибольшим кратным pбольше или равно, pᵏпотому что pᵏ⁻¹p = p.

Следовательно, мы знаем, что pᵏесть pᵏ⁻¹числа, меньшие его, которые не взаимно просты. Существуют pᵏцелые числа меньше pᵏ. Если pᵏ⁻¹не взаимно просты, то pᵏ - pᵏ⁻¹целые числа взаимно просты с pᵏ.

Для простых степеней формула подсчета взаимно простых чисел меньше, чем она: (pᵏ) = pᵏ - pᵏ⁻¹.

Для всего остального

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

Решая для n, которая имеет jпростые множители, формула произведения принимает вид:

n x (1 — 1/p₁) x (1 — 1/p₂) x ... x (1 — 1/pⱼ).

n = 42
> which has 3 prime factors
j = 3
ϕ(42) = ϕ(7 x 2 x 3) = 42 x (1 — 1/7) x (1 — 1/2) x (1 — 1/3) = 12.
ϕ(42) = 12

Один из простых множителей числа 42 равен 3. Мы знаем, что 1 из 3 чисел кратно 3, а остальные 2 из 3 — нет. Таким образом, мы умножаем 42 на , 2/3чтобы получить количество чисел меньше 42, которые не делят множитель 3.

Повторение этого процесса для всех простых чисел 42 выглядит так: 6/7 x 1/2 x 2/3 = 6/21. Это дает нам долю всех чисел меньше 42, у которых нет общих простых множителей. Чтобы получить счет, мы можем умножить пропорцию на сумму: 6/21 x 42 = 12.

Мы можем использовать это как подтверждающее доказательство и для простых степеней. Мы обнаружили, что для любой степени простого pᵏчисла общее значение равно (pᵏ) = pᵏ - pᵏ⁻¹.

pᵏ — pᵏ⁻¹
pᵏ — (pᵏ x p⁻¹)
pᵏ — (pᵏ x 1/p)
pᵏ(1 — 1/p)

Использование функции Totient

Вы в любом случае способны найти его ценность, но зачем вам это вообще? Totient Эйлера сильно опирается при работе с функцией Кармайкла, как мы видели в нашем объяснении в предыдущем посте . Следовательно, очень важна цифровая криптография.

Тотиент также имеет значение для двух нерешенных гипотез: гипотезы Лемера и гипотезы Кармайкла.

Удачной математики.

Более ?

Я пишу самый короткий информационный бюллетень в мире. Одна быстрая вещь, которую я узнал, увидел или прочитал за неделю, каждую среду.

Я хочу, чтобы это был самый доступный и актуальный информационный бюллетень, который вы получаете.

Возможно, стоит попробовать. Отписаться тоже легко.

Он называется <Еще одна вещь>. Увидимся там!