Функция Эйлера | Теория чисел
HTML-код
- Опубликовано: 31 дек 2021
- На канале Элементарная Математика было много рассказано о том, что носит имя Эйлера. Сегодня продолжим. Мы познакомимся с функцией Эйлера, которая играет важную роль в теории чисел. Обозначается функция Эйлера φ(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.
Читает Игорь Тиняков для канала Элементарная Математика
#функцияэйлера #теориячисел
Мое почтение автору видео. Этож надо видос на 47 минут в новогодние праздники сделать...
С Новым годом!
Автор не изменяет себе и каждую субботу выпускает ролик, даже если суббота выпадает на 1 января.
О, да! С Новым годом!
Благодарю автора лекции, так понятно объяснил.
Огромное спасибо за такой полезный материал!
Пожалуйста!)
Спасибо большое за отличное объяснение , и что не менее важно, за отличную и даже, в некотором роде, живую подачу!
Автору респект! Жаль, что в начале 80-хх, когда я учился в матшколе, не было ютуба ;-)
Спасибо Вам большое, очень доступно. Процветания Вашему каналу
🙏🏻
Спасибо за полезный материал!
Пожалуйста!)
Очень круто, спасибо!
Пожалуйста!)
спасибо Вам за ролики! хотелось бы увидеть больше видео про теорию чисел и теорию множеств в Вашем исполнении!
Пожалуйста!) да, эти направления думаю продолжать. По теории чисел будет пара лекций этой зимой)
Спасибо, я еще в 10 классе начал смотреть ваши лекции.
Вам спасибо, что все еще смотрите!)
Здравствуйте! Спасибо за ваши труды, канал очень интересный! А где можно посмотреть доказательство 5го утверждения? Смысл мне понятен, но но доказательство найти не могу
Здравствуйте!
Нужно всего лишь сделать аккуратно преобразования. Разложите m и n в произведение степеней простых и воспользуйтесь предыдущими утверждениями)
Ну или можете посмотреть, скажем, в википедии ru.m.wikipedia.org/wiki/Функция_Эйлера
Спасибо! Отличное видео! Будет ли видео про цепные дроби?
Пожалуйста!)
Цепные дроби в планах не стоят((
Топ.
А есть ли практическое применение этой функции ? Спасибо!
да, но не каждому это нужно. криптография, например.
А вообще этот вопрос скорее к гуглу.
Решение задачи:
Так как у чисел НОД равен d, то это число d будет в разложении обоих чисел m и n по простым, но в разложении функции Эйлера согласно 3 утверждению, оно будет встречаться лишь один раз, соответственно, можем домножить и разделить на (1-1/d) [в разложении по 3 утверждению, ведь (1-1/d) != 0 для d > 1, так как мы условились, что фи(1) = 1], тогда сомножители легко компануются в частные функции Эйлера от m и n, а также остаётся свободным множитель [1/(1-1/d)]. Он легко представим в виде [d/(d-1)]. Так как d также простое, в силу нашего разложения, то фи(d) = d - 1, согласно первому утверждению.
Отсюда верна формула: фи(mn) = фи(m) * фи(n) * (d/фи(d)), для (m, n) = d, а m, n - натуральных. ЧТД.
Да, идея верная, но зачем предполагать, что d - простое? Для упрощения написания комментария?)
В общем виде точно так же.
φ(m*n)=m*n*{П(1-1/р), входящих в d}*{П(1-1/q), входящих в m, но не входящих в d}*{П(1-1/r), входящих. в n, но не входящих в d} или для краткости φ(m*n)=m*n*{d}*{m\d}*{n\d}.
Первая скобка {d}, как Вы справедливо заметили будет встречаться лишь один раз. А для сворачивания в φ(m) и φ(n) эта скобка {d} нужна дважды.
Поэтому, как и у Вас, умножим и разделим на d*{d}=d*{П(1-1/p), входящих в d}=φ(d). И остается свернуть в числителе m*{d}*{m\d} в φ(m) и n*{d}*{n\d} в φ(n).
@@elemath я просто сразу условился разложить и m и n и d на простые, в силу основной теоремы арифметики я так могу сделать, и тогда мне без разницы какие числа, так как я могу работать с доказанным утверждением.
Можно только вопрос, если мы в пятом утверждении не будем сворачивать d - 1 в фи(d), то при взаимно простых числах, то бишь при утверждении 4, мы будем делить на 0, поэтому можем ли мы сворачивать d - 1 таким образом, и какая подоплёка под тем, что фи(1) = 1? Я понимаю по определению фи от 1: все числа не превосходящие единицу, которые взаимно просты с 1, то бишь 1 взаимно просто только с собой, но тем самым мы не можем же в утв. 5 сворачивать d - 1, так как нарушится непрерывность следования формул, то есть просто не корректна последняя замена d - 1 на фи(d)? Подскажите где я ошибаюсь. Спасибо
P.S. И вообще если мы считаем 1 простым, то можно действовать по второму утверждению: фи(1) = 1^1 - 1^0 = 0, а если оно составное, то нарушается порядок рассуждений, которые я привёл выше. Получается оно никакое: ни простое, ни составное?
@@onepiecerussia3945 Начну с конца.
1 - не является ни простым, ни составным числом. Поэтому мы тоже давайте не будем считать ее таковой.
Для любого простого числа (пусть) d справедливо φ(d)=d-1. А φ(1)=1, что следует из определения функции φ.
Утверждение 5 справедливо для любых m и n. Когда m и n - взаимно простые, то оно превращается в утверждение 4. В знаменателе будет 1, а не 0.
Ваше рассуждение не работает при d=1. Вы пишите, что φ(d)=d-1, что верно для простых чисел, но при d=1 эта формула не работает и не должна, потому как φ(1)=1, а Вы на это не обращаете внимания.
@@elemath Понял, спасибо большое! Ждём новых роликов)
Пожалуйста!)
кому интересно есть такой метод:
public int EulerFunction(int n){
int result = n;
for (int i = 2; i*i 1) result -= result / n;
return result;
}
если в таймер запихнуть отрисовку пикселя
в котором Y высчитывать через метод(X)
а X устремить от 1 до n то получится
интересный рисунок)))
'это же надо так путанно объяснить про взаимно простые числа. Причем тут одна единица?
[и зачем нужна эта функция Эйлера]
Удивительно, но именно этот вопрос я задал давеча нашему дворнику утром во дворе. "Расул, - говорю, - и зачем нужна эта функция Эйлера?"
"Экий ты невежда, - ответил мне Расул. - Вот я, мету двор и думаю о числах; подсчитываю, сколько для некоторого числа найдется других, меньших его чисел, которые с ним будут взаимно простые. Так и мысли мои, и работа моя становятся такими прекрасными, что хочется двор мести с утра до вечера. Так-то."
Выходит, что на радость дворникам нужна.