Функция Эйлера | Теория чисел

На канале Элементарная Математика было много рассказано о том, что носит имя Эйлера. Сегодня продолжим. Мы познакомимся с функцией Эйлера, которая играет важную роль в теории чисел. Обозначается функция Эйлера φ(m).
Начнем с определения, которое достаточно легкое. Надо лишь знать понятие взаимно простых чисел, с которым знакомят на уроках математики в 5 классе. Ну или в шестом.
На канале есть видео о наибольшем общем делителе    • Наименьшее общее кратное (НОК) и наиб...  . В нем разбирается также алгоритм Евклида для нахождения наибольшего общего делителя.
А сегодня мы будем оперировать исключительно натуральными числами.
Потом рассмотрим несколько простых примеров, в которых найдем значение φ(1), φ(2),..., φ(7) непосредственно по определению.
Дальше перейдем к ряду свойств, позволяющих легко и быстро находить значение функции Эйлера от любого натурального числа. Свойства, требующие доказательств, докажем.
В первом свойстве увидим чему равна функция Эйлера φ(р) от простого числа р.
Во втором свойстве научимся считать функцию Эйлера от степени простого числа р.
И далее мы увидим, как можно вычислить функцию Эйлера φ(m) от произвольного натурального числа m, разложенного в произведение простых множителей.
Далее проиллюстрируем доказательство этого свойства на конкретном примере для m=60.
Имея это свойство мы легко получим свойство мультипликативности функции Эйлера, а именно φ(m*n)=φ(m)*φ(n) для любых взаимно простых чисел m и n.
После этого уже можно находить функцию Эйлера от любого числа, но будет и еще одно утверждение, которое вам предстоит доказать самостоятельно.
Для любых двух чисел m и n (уже не обязательно взаимно простых) φ(m*n)=φ(m)*φ(n)*d/φ(d), где d - наибольший общий делитель чисел m и n.

Читает Игорь Тиняков для канала Элементарная Математика

#функцияэйлера #теориячисел