Функция Эйлера

Методы вычисления функции Эйлера. Лекция в МЭИ. За кадром осталось вычисление в виде phi(30)=30*(1-1/2)*(1-1/3)*(1-1/5) как пример реализации приведенной в лекции формулы при разложении числа на множители 30=2^1*3^1*5^1. Степени в формулу не входят.

[@MrRobotM]

Преподаватель от Бога . . . Спасибо вам большое . . .

[@jolymourner4014]

Замечательный преподаватель, большое спасибо!

[@user-sw2xr6nm6c]

45 лет как закончила школу. Послушала лекцию и помолодела. Спасибо.

[@trio9355]

Это не школьная программа

[@user-wc7en8yh3s]

@@trio9355 школьная...

[@moranyt8299]

Занимаюсь программированием, решил по приколу узнать как шифруются сообщения алгоритмом RSA. Как оказалось, алгоритм имеет внутри формулу Эйлера. Решил посмотреть ваше видео, чтобы узнать как эта функция работает. Все понятно и прекрасно объясняется, но я в очередной раз понял, почему мне не подходит очная форма обучения. В начале, каждые пару минут останавливал видео, чтобы вспомнить что означает тот или иной термин =) (или вовсе переварить информацию, объяснив ее самому себе еще раз). В жизни к сожалению такого не сделаешь, а уточнять такие простые термины как "взаимно простые числа" бывает стыдно. Благодарю за лекцию, пойду дальше изучать алгоритм =)

[@darthvader1103]

А если у нас скажем дано последовательность чисел (1,2,3,4,6,8) то как нам здесь можно применить функцию Ейлера для нахождения попарно взаимно простых чисел? Или лучше тогда воспользоваться таблицей простых чисел?

[@user-vr9uo3vb1w]

По сути, из доказанного факта сперва + fi(p1*p2)=fi(p1)*fi(p2) и выводится общая формула

[@user-ug2ij5qx2v]

Может ли чётное нетотиентное число соседствовать с простым? Может. Но только следовать за ним, но никак не предшествовать - любое число, предшествующее простому, является значением фЭ для него.

[@user-ug2ij5qx2v]

241 - 240 247 - 216 251 - 250 253 - 220 257 - 256 259 - 216 Вот некоторые значения функции Эйлера для чисел простых и кажущихся таковыми. 241, 251, 257 есть числа простые. 247, 253 и 259 - кажущиеся простыми. Интересно, вы сможете отличить числа, являющиеся простыми, от чисел, внешне похожих на простые: 391 397 401 403 407 409 851 853 857 859 863 869 871 877

[@user-ug2ij5qx2v]

Если уравнение фи(x)=n имеет решения, то их, как правило, несколько. Для n=2 x=3; 4; 6. Для n=4 x=5; 8; 10; 12. Для n=6 x=7; 9; 14; 18. Для n=8 x=15; 16; 20; 24; 30. Число n называется нетотиентным, если для него не существует соответствующего x. Наименьшее чётное - 14. Не найдено ни одного n, при котором уравнение имеет только один корень - и в то же время не доказано полное отсутствие таковых.

[@user-et3km9vg7b]

Есть задача для данного M, найти максимальное x: phi(x)=M и минимальное y: phi(y)=M. Как решать?

[@Kirsanov2011]

Я бы просто перебором решил...

[@user-ug2ij5qx2v]

Функция Эйлера для простого числа близка к 100% от этого числа. Функция Эйлера от чётного полупростого числа - к 50%. Если функция Эйлера от числа превышает 50% от него, то это число нечётное. Функция Эйлера, как и любая другая функция, имеет свой график. Только он точечный: верхняя линия напоминает график y = x-1. Средняя линия - y = x/2 - 1. Между ними точки с нечётными абсциссами, ниже средней линии - с чётными. Но и здесь можно видеть две чёткие линии - скорее всего, это ф(3p) и ф(4p).

[@Kirsanov2011]

Спасибо. Очень любопытно.

[@user-ug2ij5qx2v]

По сути, функция Эйлера от числа n - это количество несократимых правильных дробей со знаменателем n. 97 - простое число, и любая правильная дробь с этим знаменателем несократимая. Не все правильные дроби со знаменателем 91 несократимые: 6/91, 25/91, 57/91, 80/91 есть дроби несократимые. А 26/91, 49/91, 65/91, 77/91 сократить возможно: 2/7, 7/13, 5/7, 11/13.

[@user-fw9wy9ii1g]

Учусь в лицее при МЭИ. Мечтаю стать математиком. На каком факультете вы преподаёте?

[@Kirsanov2011]

ЭНМИ (читаю дискр. матем), ИТАЭ (читаю теор.мех), ИРЭ (читаю прикл.механику). Но математика однозначно самая сильная на ИВТИ . Я там раньше читал математическое моделирование. Студенты этого института традиционно побеждают на олимпиадах Москвы и России по математике. Там работают такие выдающиеся математики как А.А. Амосов, Ю.А. Дубинский и др. По математике после ИВТИ идет наш ЭНМИ (проф. Кобрин А.И., Меркурьев И.В., Подалков В.В.). Остальные институты заметно по математике отстают.

[@user-ug2ij5qx2v]

Все простые числа большие 5 делятся на 8 категорий по остатку от деления на 30: 1, 7, 11, 13, 17, 19, 23 и 29. Нетрудно догадаться, что более 2 простых чисел в одном десятке возможно только в каждом втором из трёх десятков: наибольшая концентрация простых чисел в рамках первой тысячи в десятках 1*, 10*, 19* и 82*. Только при остатке от деления на 30, равном 11, 23 или 29, можно получить другое простое число путём удвоения с последующим прибавлением единицы (простые числа Софи Жермен и соответствующие им безопасные).

[@user-im5gl2et3o]

Спасибо. Интересно. Где эта функция имеет применение?

[@Kirsanov2011]

В криптологии, везде, где работают простые числа. Она сама собой возникает в решении. Просто удобно с ней.

[@user-ug2ij5qx2v]

Перебирать все числа до 1200 на предмет взаимной простоты с ним? 1200 - число, кратное 30 и не имеющее никаких простых делителей больше 5. Здесь значение можно найти через пропорцию: 1200/30 = х/8. Отсюда х = (1200*8)/30 = 40*8 = 320.

[@iwillwatch]

а почему можно использовать пропорцию? мы же не ищем через пропорцию кол-во простых чисел меньших n. Нашли сколько простых меньших 30 и по пропорции вычислили кол-во простых меньших 1200.

[@padla6304]

если φ(p) = p-1; где p - простое число верно ли обратное? что если φ(n) = n-1 => n - простое число

[@serhiypidkuyko4206]

для двох простих чисел p,q формула phi(pq) = phi(p)phi(q) очевидна: phi(pq) = pq - (q-1) - (p-1) - 1 = (p-1)(q-1) = phi(p)phi(q) те саме з останніми двома властивостями: нехай n=2^k*m, де m непарне тоді phi(n)=phi(2^k)phi(m)=(2^k-2^{k-1})phi(m)=2^{k-1}phi(m) отже, якщо k=1, то phi(n)=phi(m); якщо k>1, то phi(n)=2*2^{k-2}phi(m)=2phi(2^{k-1}m)

[@vb3039]

Очень интерестный урок жалко что слишком урезали :(

[@david_shiko]

А куда 5 в числовом ряду делось? Оно же простое вроде как

[@Kirsanov2011]

30 делится на 5, вот и не вошло.

[@wasyauk6265]

φ(18) = φ(2 * 3 * 3) = (2 - 1)(3 - 1)(3 - 1) = 1 * 2 * 2 = 4 А должно быть 6. Почему?

[@user-nb1pf3gd4z]

Потому что, чтобы эта формула была действительна, в разложении не должно быть повторяющихся простых множителей (такие числа называются свободными от квадратов). Поэтому правильно находить так: фи(18) = фи(2*3^2) = (2 - 1)(3^2 - 3) = 1 * (9 - 3) = 6.

[@secondmodu7184]

а почему разделив по формуле фи(4) на фи(2)*фи(2) = 1*1 = 1, получаем фи(4) = 1, но в действительности фи(4) = 2 ?

[@user-ug2ij5qx2v]

Потому что эта формула действительна не для любых a и b, а только для взаимно простых!

[@iron_777]

Дядька то умный

[@komronbek2064]

[@user-sd2tq3jf3x]

Дали похожую задачу, при трудоустройстве на работу.

[@exploitation_rutm7606]

Куда устраивался?

[@muxaeotob2369]

Да, но мультипликативность функции эйлера не доказана ж ведь

[@TurboGamasek228]

2*2=4

[@istinaanitsi3342]

а чем 3 и 5 не угодили?

[@yaggod1706]

Функций эйлера - количество ВЗАИМНО ПРОСТЫХ, то есть чисел, не имеющих общих делителей. В случае с 3 и 5 общими делителями будут являться сами числа

[@user-oy6de7zg2x]

Ребята, кто с термехом может помочь?

[@Kirsanov2011]

Я во вторник 4-го февр после 13.30 и до 15 буду в МЭИ, кафедра теор мех (РМДиПМ), Москва, Красноказарменная 13, корп. С, ауд С216. Расскажу беспл.

[@user-oy6de7zg2x]

как можно связаться ватсапе?

[@dizogdizog2591]

М... Да уж... А доказательство мультипликативности было? Так чисто... Оно не сложное конечно. Это школьная математика (для нормального прилежного и в меру талантливого школьника)

[@annavasileva5688]

И всё же... Для чего нужна эта функция то?

[@Kirsanov2011]

Например, в криптографии. Там все основано на простых числах. А у простых чисел есть важное свойство - они непредсказуемы. Вот и шифры на них надежнее.

[@AB-ex4iu]

@@Kirsanov2011 я как раз разбираю алгоритм шифрования RSA. Но до сих пор не понимаю, для чего он нужен там. С простыми числами это одно, а зачем там нужно находить именно КОЛИЧЕСТВО взаимно простых, я не понимаю. С любым успехом я могу взять рандомно простое число меньше модуля.

[@Kirsanov2011]

Из Википедии (ф-я Эйлера) На этапе создания пары из секретного и открытого ключей вычисляется {\displaystyle \varphi (n)=\varphi (p\cdot q)=(p-1)\cdot (q-1),}\varphi(n) = \varphi(p \cdot q) = (p-1) \cdot (q-1), где {\displaystyle p}p и {\displaystyle q}q - простые. Затем выбираются случайные числа {\displaystyle d,\ e}{\displaystyle d,\ e} так, чтобы {\displaystyle d\cdot e=1\;{\bmod {\;}}\varphi (n).}d \cdot e = 1 \;\bmod \;\varphi(n). Затем сообщение шифруется открытым ключом адресата: {\displaystyle c=m^{e}\;{\bmod {\;}}n.}c = m^e \;\bmod \;n. После этого расшифровать сообщение может только обладатель секретного ключа {\displaystyle d}d: {\displaystyle m=c^{d}\;{\bmod {\;}}n.}m = c^d \;\bmod \;n. Корректность последнего утверждения основывается на теореме Эйлера и китайской теореме об остатках.

[@user-uk4nn6sx1v]

это функция так и в жизни мне не пригодилась

[@mikegemini9503]

Для начала, было-бы здорово, если-бы объяснили понятие (здесь объяснения не видно! И для меня - глупого в математике, всё не так очевидно, как для тех кто "прошарил" тему), а то ряд простых чисел... а где 5, 3? Из объяснения не совсем понятно.

[@mamakermit]

Здесь имеется в виду не "ряд простых чисел", а ВЗАИМНО простые числа, то есть не имеющие с аргументом никаких общих делителей, кроме 1. В примере с phi(30) числа 3 и 5 к взаимно простым с 30 не относятся. А вот в случае с 11 как раз все числа от 1 до 10 будут с ним взаимно простыми (так как само 11 простое и не делится ни на что, кроме 1 и 11). Именно поэтому phi(30) = 8, а скажем phi(29) = 28

[@user-io5xg9rt7o]

Вы говорили фи( n)меньше чем n и пишите фи (1)=1

[@user-mw1lk5zm8b]

Це можна сприймати як факт, що phi(1)=1. Або розуміти це так, як те що (1,1)=1, де перша одиниця це наше число, друга одиниця це одиниця з якою порівнюєм, ну і зрозуміло, що НСД(1,1)=1...тобто інакше кажучи 1 це єдине число, яке є взаємно просте само з собою...крім того, функція Ейлера phi(n) вказує кількість взаємно простих чисел менших або рівних n, при n>1,зрозуміло що n не є взаємно просте з собою...