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

  Рет қаралды 61,435

Kirsanov2011

Kirsanov2011

9 жыл бұрын

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

Пікірлер: 54
@MrRobotM
@MrRobotM Жыл бұрын
Преподаватель от Бога . . . Спасибо вам большое . . .
@jolymourner4014
@jolymourner4014 2 жыл бұрын
Замечательный преподаватель, большое спасибо!
@user-sw2xr6nm6c
@user-sw2xr6nm6c 4 жыл бұрын
45 лет как закончила школу. Послушала лекцию и помолодела. Спасибо.
@trio9355
@trio9355 3 жыл бұрын
Это не школьная программа
@user-wc7en8yh3s
@user-wc7en8yh3s 2 жыл бұрын
@@trio9355 школьная...
@moranyt8299
@moranyt8299 5 ай бұрын
Занимаюсь программированием, решил по приколу узнать как шифруются сообщения алгоритмом RSA. Как оказалось, алгоритм имеет внутри формулу Эйлера. Решил посмотреть ваше видео, чтобы узнать как эта функция работает. Все понятно и прекрасно объясняется, но я в очередной раз понял, почему мне не подходит очная форма обучения. В начале, каждые пару минут останавливал видео, чтобы вспомнить что означает тот или иной термин =) (или вовсе переварить информацию, объяснив ее самому себе еще раз). В жизни к сожалению такого не сделаешь, а уточнять такие простые термины как "взаимно простые числа" бывает стыдно. Благодарю за лекцию, пойду дальше изучать алгоритм =)
@user-ug2ij5qx2v
@user-ug2ij5qx2v 5 жыл бұрын
Может ли чётное нетотиентное число соседствовать с простым? Может. Но только следовать за ним, но никак не предшествовать - любое число, предшествующее простому, является значением фЭ для него.
@darthvader1103
@darthvader1103 8 жыл бұрын
А если у нас скажем дано последовательность чисел (1,2,3,4,6,8) то как нам здесь можно применить функцию Ейлера для нахождения попарно взаимно простых чисел? Или лучше тогда воспользоваться таблицей простых чисел?
@user-ug2ij5qx2v
@user-ug2ij5qx2v 7 жыл бұрын
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
@user-ug2ij5qx2v 5 жыл бұрын
Если уравнение фи(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-ug2ij5qx2v
@user-ug2ij5qx2v 7 жыл бұрын
По сути, функция Эйлера от числа 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-ug2ij5qx2v
@user-ug2ij5qx2v 7 жыл бұрын
Все простые числа большие 5 делятся на 8 категорий по остатку от деления на 30: 1, 7, 11, 13, 17, 19, 23 и 29. Нетрудно догадаться, что более 2 простых чисел в одном десятке возможно только в каждом втором из трёх десятков: наибольшая концентрация простых чисел в рамках первой тысячи в десятках 1*, 10*, 19* и 82*. Только при остатке от деления на 30, равном 11, 23 или 29, можно получить другое простое число путём удвоения с последующим прибавлением единицы (простые числа Софи Жермен и соответствующие им безопасные).
@user-ug2ij5qx2v
@user-ug2ij5qx2v 7 жыл бұрын
Функция Эйлера для простого числа близка к 100% от этого числа. Функция Эйлера от чётного полупростого числа - к 50%. Если функция Эйлера от числа превышает 50% от него, то это число нечётное. Функция Эйлера, как и любая другая функция, имеет свой график. Только он точечный: верхняя линия напоминает график y = x-1. Средняя линия - y = x/2 - 1. Между ними точки с нечётными абсциссами, ниже средней линии - с чётными. Но и здесь можно видеть две чёткие линии - скорее всего, это ф(3p) и ф(4p).
@Kirsanov2011
@Kirsanov2011 7 жыл бұрын
Спасибо. Очень любопытно.
@user-ug2ij5qx2v
@user-ug2ij5qx2v 5 жыл бұрын
Перебирать все числа до 1200 на предмет взаимной простоты с ним? 1200 - число, кратное 30 и не имеющее никаких простых делителей больше 5. Здесь значение можно найти через пропорцию: 1200/30 = х/8. Отсюда х = (1200*8)/30 = 40*8 = 320.
@iwillwatch
@iwillwatch 5 жыл бұрын
а почему можно использовать пропорцию? мы же не ищем через пропорцию кол-во простых чисел меньших n. Нашли сколько простых меньших 30 и по пропорции вычислили кол-во простых меньших 1200.
@user-et3km9vg7b
@user-et3km9vg7b 7 жыл бұрын
Есть задача для данного M, найти максимальное x: phi(x)=M и минимальное y: phi(y)=M. Как решать?
@Kirsanov2011
@Kirsanov2011 7 жыл бұрын
Я бы просто перебором решил...
@user-vr9uo3vb1w
@user-vr9uo3vb1w 2 ай бұрын
По сути, из доказанного факта сперва + fi(p1*p2)=fi(p1)*fi(p2) и выводится общая формула
@user-fw9wy9ii1g
@user-fw9wy9ii1g 2 жыл бұрын
Учусь в лицее при МЭИ. Мечтаю стать математиком. На каком факультете вы преподаёте?
@Kirsanov2011
@Kirsanov2011 2 жыл бұрын
ЭНМИ (читаю дискр. матем), ИТАЭ (читаю теор.мех), ИРЭ (читаю прикл.механику). Но математика однозначно самая сильная на ИВТИ . Я там раньше читал математическое моделирование. Студенты этого института традиционно побеждают на олимпиадах Москвы и России по математике. Там работают такие выдающиеся математики как А.А. Амосов, Ю.А. Дубинский и др. По математике после ИВТИ идет наш ЭНМИ (проф. Кобрин А.И., Меркурьев И.В., Подалков В.В.). Остальные институты заметно по математике отстают.
@user-im5gl2et3o
@user-im5gl2et3o 2 жыл бұрын
Спасибо. Интересно. Где эта функция имеет применение?
@Kirsanov2011
@Kirsanov2011 2 жыл бұрын
В криптологии, везде, где работают простые числа. Она сама собой возникает в решении. Просто удобно с ней.
@padla6304
@padla6304 Жыл бұрын
если φ(p) = p-1; где p - простое число верно ли обратное? что если φ(n) = n-1 => n - простое число
@serhiypidkuyko4206
@serhiypidkuyko4206 5 жыл бұрын
для двох простих чисел 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
@vb3039 2 жыл бұрын
Очень интерестный урок жалко что слишком урезали :(
@david_shiko
@david_shiko 4 жыл бұрын
А куда 5 в числовом ряду делось? Оно же простое вроде как
@Kirsanov2011
@Kirsanov2011 4 жыл бұрын
30 делится на 5, вот и не вошло.
@wasyauk6265
@wasyauk6265 3 жыл бұрын
φ(18) = φ(2 * 3 * 3) = (2 - 1)(3 - 1)(3 - 1) = 1 * 2 * 2 = 4 А должно быть 6. Почему?
@user-nb1pf3gd4z
@user-nb1pf3gd4z 2 жыл бұрын
Потому что, чтобы эта формула была действительна, в разложении не должно быть повторяющихся простых множителей (такие числа называются свободными от квадратов). Поэтому правильно находить так: фи(18) = фи(2*3^2) = (2 - 1)(3^2 - 3) = 1 * (9 - 3) = 6.
@user-sd2tq3jf3x
@user-sd2tq3jf3x 4 жыл бұрын
Дали похожую задачу, при трудоустройстве на работу.
@exploitation_rutm7606
@exploitation_rutm7606 3 жыл бұрын
Куда устраивался?
@iron_777
@iron_777 3 жыл бұрын
Дядька то умный
@komronbek2064
@komronbek2064 Жыл бұрын
@muxaeotob2369
@muxaeotob2369 Жыл бұрын
Да, но мультипликативность функции эйлера не доказана ж ведь
@secondmodu7184
@secondmodu7184 7 жыл бұрын
а почему разделив по формуле фи(4) на фи(2)*фи(2) = 1*1 = 1, получаем фи(4) = 1, но в действительности фи(4) = 2 ?
@user-ug2ij5qx2v
@user-ug2ij5qx2v 7 жыл бұрын
Потому что эта формула действительна не для любых a и b, а только для взаимно простых!
@TurboGamasek228
@TurboGamasek228 3 жыл бұрын
2*2=4
@user-oy6de7zg2x
@user-oy6de7zg2x 4 жыл бұрын
Ребята, кто с термехом может помочь?
@Kirsanov2011
@Kirsanov2011 4 жыл бұрын
Я во вторник 4-го февр после 13.30 и до 15 буду в МЭИ, кафедра теор мех (РМДиПМ), Москва, Красноказарменная 13, корп. С, ауд С216. Расскажу беспл.
@user-oy6de7zg2x
@user-oy6de7zg2x 4 жыл бұрын
как можно связаться ватсапе?
@istinaanitsi3342
@istinaanitsi3342 3 жыл бұрын
а чем 3 и 5 не угодили?
@yaggod1706
@yaggod1706 3 жыл бұрын
Функций эйлера - количество ВЗАИМНО ПРОСТЫХ, то есть чисел, не имеющих общих делителей. В случае с 3 и 5 общими делителями будут являться сами числа
@dizogdizog2591
@dizogdizog2591 Жыл бұрын
М... Да уж... А доказательство мультипликативности было? Так чисто... Оно не сложное конечно. Это школьная математика (для нормального прилежного и в меру талантливого школьника)
@annavasileva5688
@annavasileva5688 Жыл бұрын
И всё же... Для чего нужна эта функция то?
@Kirsanov2011
@Kirsanov2011 Жыл бұрын
Например, в криптографии. Там все основано на простых числах. А у простых чисел есть важное свойство - они непредсказуемы. Вот и шифры на них надежнее.
@AB-ex4iu
@AB-ex4iu Жыл бұрын
@@Kirsanov2011 я как раз разбираю алгоритм шифрования RSA. Но до сих пор не понимаю, для чего он нужен там. С простыми числами это одно, а зачем там нужно находить именно КОЛИЧЕСТВО взаимно простых, я не понимаю. С любым успехом я могу взять рандомно простое число меньше модуля.
@Kirsanov2011
@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
@user-uk4nn6sx1v 2 ай бұрын
это функция так и в жизни мне не пригодилась
@user-io5xg9rt7o
@user-io5xg9rt7o 4 жыл бұрын
Вы говорили фи( n)меньше чем n и пишите фи (1)=1
@user-mw1lk5zm8b
@user-mw1lk5zm8b 4 жыл бұрын
Це можна сприймати як факт, що phi(1)=1. Або розуміти це так, як те що (1,1)=1, де перша одиниця це наше число, друга одиниця це одиниця з якою порівнюєм, ну і зрозуміло, що НСД(1,1)=1...тобто інакше кажучи 1 це єдине число, яке є взаємно просте само з собою...крім того, функція Ейлера phi(n) вказує кількість взаємно простих чисел менших або рівних n, при n>1,зрозуміло що n не є взаємно просте з собою...
@mikegemini9503
@mikegemini9503 6 жыл бұрын
Для начала, было-бы здорово, если-бы объяснили понятие (здесь объяснения не видно! И для меня - глупого в математике, всё не так очевидно, как для тех кто "прошарил" тему), а то ряд простых чисел... а где 5, 3? Из объяснения не совсем понятно.
@mamakermit
@mamakermit 5 жыл бұрын
Здесь имеется в виду не "ряд простых чисел", а ВЗАИМНО простые числа, то есть не имеющие с аргументом никаких общих делителей, кроме 1. В примере с phi(30) числа 3 и 5 к взаимно простым с 30 не относятся. А вот в случае с 11 как раз все числа от 1 до 10 будут с ним взаимно простыми (так как само 11 простое и не делится ни на что, кроме 1 и 11). Именно поэтому phi(30) = 8, а скажем phi(29) = 28
Задача логики для детектива
5:23
Kirsanov2011
Рет қаралды 362 М.
TRY NOT TO LAUGH 😂
00:56
Feinxy
Рет қаралды 12 МЛН
Задача Бюффона об игле
8:45
Kirsanov2011
Рет қаралды 153 М.
Интересное уравнение, однако...
15:27
matemrepetitor
Рет қаралды 3,4 М.
Великая теорема Ферма
19:22
Маткульт-привет! :: Алексей Савватеев и Ко
Рет қаралды 874 М.
Функция Эйлера | Теория чисел
46:49
Элементарная Математика
Рет қаралды 7 М.
Смысл интеграла и производной. В помощь студенту
15:54
Лекция 10. Экспонента и её смысл.
14:37
Лекции по математике профессора Власова В.Г. для школьников 10-11 классов
Рет қаралды 46 М.