Малая теорема Ферма и теорема Эйлера | Ботай со мной

#БотайСоМной #037
Малая теорема Ферма и теорема Эйлера
Перед просмотром этого видео посмотрите ролик "Сравнение по модулю. Арифметика остатков": • ✓ Сравнение по модулю....
Мини-курс про сравнение по модулю: foxford.ru/cou...
(Делимость, сравнения по модулю, теоремы Ферма и Эйлера, квадратичные вычеты)
Заявки на следующие ролики: youtubetrushin....
Библиотека курсов онлайн-школы Фоксфорд: foxford.ru/lib...
Онлайн-курсы с Борисом Трушиным:
11 класс. Подготовка к ЕГЭ по математике. Часть C (задания 13-19):
foxford.ru/cou...
11 класс. Подготовка к ЕГЭ по математике. Часть B (задания 1-12):
foxford.ru/cou...
10 класс. Подготовка к ЕГЭ по математике:
foxford.ru/cou...
9 класс. Подготовка к ОГЭ по математике:
foxford.ru/cou...
Личный сайт: TrushinBV.ru
ЕГЭ и ОГЭ по математике | Борис Трушин: ege_tru...
Группа сайта TrushinBV.ru: trushin...
Личная страница: trushinbv
Группа сайта: / trushinbv
Личная страница: / boris.trushin
KZbin-канал: / trushinbv

[@trushinbv]

#БотайСоМной #037 Малая теорема Ферма и теорема Эйлера Перед просмотром этого видео посмотрите ролик "Сравнение по модулю. Арифметика остатков": kzbin.info/www/bejne/onnKfpxul5dqd5Y Мини-курс про сравнение по модулю: foxford.ru/courses/1170/landing?ref=p308_yt& (Делимость, сравнения по модулю, теоремы Ферма и Эйлера, квадратичные вычеты) Заявки на следующие ролики: youtubetrushin.reformal.ru/

[@altair2899]

Прям вплотную подошли к теореме Лагранжа и определению группы. Когда-то такое может появиться на канале?

[@trushinbv]

@@altair2899, может. Если будет достаточное количество интересующихся. Например, если это видео посмотрит тысяч 10 человек, или здесь -- youtubetrushin.reformal.ru/ -- этот запрос будет популярен.

[@trushinbv]

@@powerofwisdom2336, да. Но, многие остановятся только на первом. А кому-то понять второе без первого не так просто. Но, вы правы, конечно.

[@logofilm2321]

Борис Трушин ,а вы сможете доказать большую теорему ферма???

[@Shtokalo]

@@trushinbv 13 к посмотрели

[@amikalen1857]

Жду видео больше чем свое день рождение

[@karelalex]

Когда так любишь математику, что забил на ЕГЭ по русскому.

[@Ramatreeman]

Ура! Обожаю теорию чисел ^u^

[@dashqw]

Спасибо большое, в унике нормально не объясняют, очень выручили в подготовке к контрольной!

[@IgorGusev28]

Борис Викторович, привет! Спасибо за ролик! Теория сравнений Гаусса раньше не была мне знакома. Только не так давно (сын учился в ФТШ, есть такая физмат школа в Питере) я узнал про это. Очень красивая теория. Но, вот каким соображением я хотел бы поделиться с Вами: Доказывая Th Эйлера, Вы сформулировали, что функция Эйлера это количество натуральных чисел меньших некоторого натурального n и взаимно простых с ним, и далее (немного резануло слух) Вы сказали, т.е не имеющих общих делителей с n. Но, 1 имеет общий делитель с любым натуральным числом n, - собственно, единицу. Строго говоря, высказывание "количество натуральных чисел меньших некоторого натурального n и взаимно простых с ним" не эквивалентно высказыванию: "количество натуральных чисел меньших некоторого натурального n и не имеющих общих делителей с n". Просто, сформулировав, что взаимная простота и отсутствие общих делителей, - это одно и тоже, Вы затем (вместо фразы "взаимно просты c n") употребляете каждый раз фразу: "не имеют общих делителей c n". Тем самым, каждый раз, исключая единичку, из приведённой системы вычетов. Владимир Борисович, хочу искренне поблагодарить Вас за контент, который Вы производите, - очень много интересного, главное в понятном изложении, с крутыми фишками (например, про количество слов, которые можно составить из букв в словах ТРУШИН и МАТЕМАТИКА, с неожиданным затем переходом (через это) к понятию сочетаний из n по k, - круто! И у вас много в роликах таких "находок"). За теорию чисел отдельное спасибо! По вашему совету прошёл по ссылке, купил у Фоксорда курс Дмитрия Максимова (в записи), уже посмотрел где-то половину. Кстати, любопытно, что он там (на одном из занятий) показывает задачку, которая была и у Вас в видео "Задачи на доказательство делимости. Малая теорема Ферма": - Докажите, что для натурального n, целое число (2^n - 1)^n - 3 делится на (2^n - 3) Борис Викторович, а не подскажите из какого задачника это? С благодарностью, Игорь.

[@One-androgyne]

Захватывающие объяснение! А вон оно как устроено все, а я голову ломал, спасибо за превосходное объяснение

[@antont.9249]

Просто и лаконично! Борис, спасибо!

[@cosyx]

Спасибо за видео, очень информативно) Было бы интересно ещё послушать про теорию графов, связанные с этим олимпиадные задачи на знакомства и т.п.

[@trushinbv]

Пишите сюда -- youtubetrushin.reformal.ru/ ;-)

[@ОлегОлег-е9у7п]

Привет слушателям!!'' а так,,же владельцу этого видео. Что я здесь хочу вам сказать, и так сказать что у меня имеется решение и либо ответ для этой задачи n = 7, 4 ,3. Что ответ этой задачи настолько легкий мне хотелось тут чтобы это проверили, если вам интересна! эта информация; напишите мне ответ. Всем пока.

[@AntiChrist5179]

наконец то я понял эту теорему . лайк однозначно

[@gjk9119]

Спасибо огромное, Борис, я готовлюсь к обучению в вузе и в нашей брошюре доказательство было какое то размытое, а тут всё сразу ясно

[@АхадАдыширинов]

Очень круто и красиво!) К сожалению, не все могут так доходчиво объяснять

[@dima_math]

Отличное видео! Побольше бы таких!

[@annaponomarova3472]

Классный ролик, спасибо!

[@nobrainnogain7255]

Борис Викторович, это видео просто оч классное, как и серия роликов про начала ТЧ, в школе теорию чисел с комбинаторикой обходят стороной, а у вас можно найти поистине удивительный контент, спасибо огромное, особенно про th. Эйлера в ТЧ, было очень интересно, но все же должен признать, что док-во МТФ которое вы показывали в задачке по комбинаторике более 'красивое', что ли. Сделайте пожалуйста видео о сумме квадратов первых n чисел в k-той степени, пожаааалуйста.

[@humaniora_for_all]

Спасибо! Мне кажется, такие темы очень нужны. Если ученик в школе не выходит за пределы школьной программмы, ему трудно будет в университете.

[@mistrebrown7642]

Борис, было бы здорово, если бы вы всегда для общих формул параллельно рассматривали пример на вполне конкретных значениях(как вы делаете это, начиная с 13:48). А так: всё круто, всё понятно, спасибо!

[@tmbo-ri3hk]

Мегакруто!

[@dziumka_chan]

Спасибо,очень интересно и доступно❤️

[@skm6859]

все замечательно )

[@arrrrrigomenjo]

Спасибо! Я смог сдать экзамен!

[@crazufithman2737]

Класс!

[@whereispie]

Опять лучший), спасибо

[@valentinaleks4346]

Все оч. оч. интересно. Для людей, которые не математики и не физики было бы интересно знать - как то или иное достижение в этих областях помогло в решении конкретных проблем. Хотя бы несколько конкретных примеров. Например тория относительности, почти понятно, помогла в работе Гланас.

[@ДмитрийЧернов-ъ2ф]

Современная криптография в системах связи построена на базе теоремы Эйлера.

[@Rhebddbxbdhr]

Спасибо чел

[@НовокузнецкиеСомелье]

мтф через теорему лагранжа красиво доказывается

[@vadimfilippovchit97]

Информативно :^}

[@MonaLisa_667]

супер

[@A1xarT]

Доказательство малой теоремы суперкрасивое и запоминающееся

[@ПолиграфПолиграфыч-х5т]

Самый длинный час в моей жизни...

[@factualinfomation7807]

хорош мужик)

[@ИринаБондарь-л6п]

Спасибо!

[@alexeydmitriev1681]

В определении phi(n) должно быть

[@Гольяновская]

14:18 Очень пятёрка красивая)

[@ilyabikmeev]

Здравствуйте Борис) Можно ли записать видео по китайской теореме об остатках?

[@_Yes_.]

Я борис с альтернативного аккаунта и пишу вам нет

[@quadroninja2708]

@@_Yes_. ты максимум кот Борис из рекламы кошачьего корма

[@pavelsavenkov7827]

@Борис Трушин, спасибо за очень ясные объяснения. Я заметил, что при доказательстве Теоремы Эйлера в 16:45 Вы пытаетесь доказать то, что изначально было взято, как исходное условие в 13:13: 13:13 Давайте выпишим все вот эти вот Фи от n чисел - все различные числа от 1 до (n - 1), которые не имеют с n общих делителей kzbin.info/www/bejne/eIusi31opcx7eMk 16:45 Давайте поймем, что они не только разные, а что они немогут иметь с n общих делителей kzbin.info/www/bejne/eIusi31opcx7eMk

[@yury.malay300]

Из ac сравнимо с bv по модулю m не следует , что a сравнимо с b по модулю m , так как Zm кольцо у которого могут быть делители нуля , а значит закон сокращения не работает. Но если m- простое число , то как следует из интуитивного рассуждений ( ну или факта , что Zm -поле ) следует , что a сравнимо с b по модулю m.

[@jenik6210]

Спасибо

[@dmanikhine]

Большое спасибо за видео с доказательствами теорем. Возможно ли обновить ссылку на "Мини-курс про сравнение по модулю:"? Или курса больше нет в продаже?

[@maligosssaron3416]

Скорее курс по теории чисел)

[@atabek3568]

2:32 Можно делить но не сокращать, когда делим на 2, делитель теперь будет не 4 а 2.

[@kuchma19]

Может поговорите про аффинные преобразования?

[@leramalakhova]

Ни одного дизлайка)

[@БейбарысЖеңісбек]

7:52 называется "полная система вычетов", если хотите еще что то про это узнать (я сомневаюсь, что жюри всероса не знает это, кажется просто не хотел инфой перегружать) Так же МТФ можно доказать через бином ньютона (a+b)^p=a^p+b^p (mod p)

[@trushinbv]

А как отсюда следует мтф?

[@БейбарысЖеңісбек]

@@trushinbv Похоже, никак.(да, можно это как фуры решать и доказать для 2 с помощью P(a;a), но вряд-ли получится для всех целых). Как то это у меня в памяти отпечаталась как док-во мтф. Это по идет следствие мтф. Я это доказывал сразу после того как разобрался с системой вычетов, и док-во мультипликативности функции эйлера. Наверное из за этого путаница

[@БейбарысЖеңісбек]

​@@trushinbv А вот и нет, оказывается следует. Как то ехал на подготовку к олимпам в другой город перед заклом, и нам дали эту задачу на разминку. Там и доказал, что от сюда следует мтф Вот док-во: (a+b)^p=a^p+b^p mod p Предположение индукции: x^p=x mod p База: ставим a=b=1 и выводим базу для x=2 Тогда пусть x^p=x mod p (!) (x+1)^p=x+1 mod p А это верно, так как (x+1)^p=x^p+1^p=x^p+1=x+1 mod p

[@trushinbv]

@@БейбарысЖеңісбека, да. Симпатично )

[@somebody198]

"Ни одно из чисел от 1 до (p-1) не делится p,потому что p - простое,а все числа меньше p". Борис Викторович,а зачем вы уточнили,что p простое,достаточно ведь того,что все числа меньше p,разве нет?

[@trushinbv]

Да, здесь конкретно здесь это было не важно. Это скорее для того, чтобы из того, что ни a, и ни одно из них не делится на p^ следует, что ни одно из произведений на p не делится.

[@trushinbv]

@@powerofwisdom2336, имеется в виду, что в самой фразе "Ни одно из чисел от 1 до (p-1) не делится p, потому что p -- простое, а все числа меньше p" часть про "потому что p -- простое," лишняя.

[@Даня-р3п2б]

Теперь только БТФ!!

[@42-94]

Алгебраическая геома ВПЕРЕД

[@ЗемфирЗемфиров-з7б]

про гипотезу Римана искал) и попал сюда

[@kuchma19]

Еще про инверсию можно поговорить

[@Toropigeon]

Вопрос не по теме. Когда, например, в условии написано, что число бесконечно мало, оно стремится к нулю или к минус бесконечности?

[@trushinbv]

Число не может быть бесконечно мало. Бесконечно малой бывает последовательность, это означает, что она стремится к нулю. Это, кстати, будет следующим видео в #матан

[@marshall366]

4:42 там разве не равносильность в утверждении( Б. В. говорит, что следствие)?

[@ЕгорРябцев-ь8м]

Борис, доброе время суток. Не могу найти видео, в котором вы говорили что делать , если уровень в геометрии близок нулю ( вы рекомендовали какие - то задачники), которые помогают подготовиться к Геометрии в ЕГЭ. Подскажите ещё раз, спасибо.

[@Axion245]

kzbin.info/www/bejne/mIW2g4dteZ5qg9U

[@kuchma19]

kzbin.info/www/bejne/mIW2g4dteZ5qg9U

[@DonSPBLegogames]

Борис Викторович, здравствуйте Видео, конечно, довольно старое, но, надеюсь, вы увидите этот комментарий Только что вернулся с заваленого зачёта по мат логике Попался билет по свойствам сравнений (его написал без проблем), но вот на доп вопросе меня завалили Он звучал так: "При каком условии можно в выражении ac=bc(mod m) можно сократить c" Я ответил, как было в свойствах (и у вас в видео): "При НОД(m, c) =1" Мне сказали, что есть ещё один способ это сделать и послали на пересдачу, причём не объяснив что это за способ.. Пожалуйста, расскажите как всё же можно ещё сократить с в данном выражении, а то не хочется второй раз на том же валиться

[@СергейСкородумов-ь7ъ]

Если a, b, m делятся на с, то всё можно сократить на с

[@human3336]

Когда a=b

[@matanmaster]

Интересно причем тут матлогика вообще?

[@zlukich]

Не совсем понял момент вначале, что на с можно сократить если m и с не имеют общих делителей кроме 1. А например 12 сравнимо с 8 по модулю 2, и 6 сравнимо с 4 по модулю 2. Сократили на двойку, а все равно верно, хотя НОД у двух чисел равен 2, как такое возможно?

[@trushinbv]

А в чем противоречие? Я же не сказал, что только в этом случае можно сократить

[@MaxPV1981]

@@trushinbv Вы именно так и сказали на 3:15 - "... Единственная возможность, когда можно сократить...". Проверяем: 27 - 9 делится на 6, сокращаем на 3, нод для 3 и 6 - 3, 9 - 3 тоже делится на 6. Тут я завис. И такие противоречия мешают воспринимать дальнейший материал, т.к. думаешь, что чего-то пропустил. Видимо, только мы с Арсением действительно пытались понять :)

[@elliotalderson6609]

@@MaxPV1981 Да, видимо только вы "пытались", а остальные поняли

[@MaxPV1981]

@@elliotalderson6609 Ну раз поняли, то объясните противоречие.

[@ywbc1217]

Да, ОЧЕНЬ грубая неточность в видео но всем пофиг -- "

[@sergeiivanov5739]

Борис Викторович Трушин, вопрос не по теме. Всегда хотел узнать, а почему - речь идёт об экстремумах - мы наблюдаем минимум в случае положительности второй производной? То есть есть функция y = f(x) такая, что D(f) = R и E(f) = R. Мы нашли производную и решили уравнение f'(x) = 0, в результате чего нашли точку (допустим одну) x0. Затем нашли вторую производную и подставили x0 туда. И пусть получили, что f''(x0) > 0. Поэтому x0 - точка минимума. Почему так? С параболой все верно (там именно так и выходит, ибо вторая ее производная суть 2a).

[@trushinbv]

Если вторая производная положительная, то первая производная возрастает. Но если она в самой точке равна нулю, значит до точки она отрицательна, а после -- положительна. Значит сама функция до точки убывает, а после -- возрастает.

[@СтаниславВ-о5ю]

Них-я не понятно! Но очень интересно!

[@dovrenempire4682]

Можно видео про формулу d^2=R^2-2Rr и расстояния между центрами окружности

[@neo7244]

БВ, здравствуйте ! Видео конечно старое, но вдруг мое сообщение дойдет до вас. Посмотрел прошлое видео про сравнение модулей, все понял, решил много задач такого типа. Сейчас попробовал сделать тоже самое(с подходящими, конечно, числами), но ответ всегда разный. Попробовал пока что только с МТФ, в каждом случаи получается что остаток 1. Уже пару раз посмотрел видео, вроде все правила соблюдаю, в чем тогда проблема ? Заранее спасибо!

[@neo7244]

Дополню комментарий конкретным примером. Берем число 409 в 651 степени и пробуем находить остаток при делении на 23. По методу прошлого видео получается 2, проверил, все правильно. А если использовать МТФ, то ответ будет 1

[@trushinbv]

А как вы МВФ используете?

[@neo7244]

@@trushinbv Так как числа взаимно простые, а 409 не делится на 23, следовательно можно использовать МТФ. В таком случаи, 409 в степени 22 эквивалентно 1. Отсюда можно сделать вывод что 409 в к степени эквивалентно 1 в к степени. И таким образом получается, что остаток от деления независимо от числа будет 1

[@trushinbv]

@@neo7244 409^651 = (409^22)^29 * 409^13 = 1^29 * 18^13 = 324^6 * 18 = 2^6 * 18 = 64 * 18 = (-5) * (-5) = 25 = 2

[@ywbc1217]

НА САМОМ ДЕЛЕ ПРАВИЛЬНОО ТАК: СОКРАШАТЬ ВСЕГДА МОЖНО НА МНОЖИТЕЛЬ, КОТОРЫЙ НЕ ИМЕЕТ ОБЩИЙ ДЕЛИТЕЛЬ С m НО СОКРАШАТЬ ТАКЖЕ ИНОГДА МОЖНО И НА МНОЖИТЕЛЬ, КОТОРЫЙ ИМЕЕТ ОБЩИЙ ДЕЛИТЕЛЬ С m ----------------------------- например: c = 5 m = 25 a = 3 b = 28 Борис 3 раза (ТРИ РАЗА !!!!!) в видео говорит, что сокращать можно, НО ТОЛЬКО при условии, что c и m не имеют общего делителя. Это большая неточность. Хотя всё остальное изложение (логика) БЛЕСТЯЩЕ !!! БОЛЬШОЕ СПАСИБО БОРИС! я в шоке ))))))))))))

[@lol-rt5te]

Не понимаю что ты хотел этим доказать, потому что ac по прежнему не сравнимо с bc по модулю m. Да, есть свойство которое говорит, что можно сокращать, но в его условии сказано, что существует общий делитель a, b, m равный каково нибудь d. В таком случае, если сравнимы a и b по модулю m, то сравнимы a/d и b/d по модулю m/d

[@ywbc1217]

@@lol-rt5te посчитай ещё раз ac сравнимо с bc по модулю m и впредь, будь внимательней )

[@Командор-ч2ю]

Тоже сразу подумал бред какой-то, если только взаимнопросты c и m

[@lol-rt5te]

@@ywbc1217 Ну давай посчитаем. Напиши потом конкретное место где я ошибся. По определению числа сравнимы по модулю m тогда и только тогда, когда равны из остатки от деления на m. ( тут ошибки быть не может ) Ну тогда 3×5=15, остаток от деления 15 на 25 ( m= 25 ) равен 15. ( тут я тоже думаю, ошибки нет ). 28×3=84, остаток от деления 84 на 25 равен 9( проверил для тебя на калькуляторе, все верно). 9≠15, а значит числа 3×15 и 3×28 не сравнимы по модулю 25. Жду.

[@Sasha-vn8dq]

@@lol-rt5te 28 на 5 умножаем, а не на 3.

[@P34-h8q]

БВ, а если и *с* и *а-б* делятся на m? Ведь нам можно сократить в случае: 6•4=2•4 (mod 4)

[@mistrebrown7642]

@Борис Трушин хотелось бы комментарий по этому поводу

[@mistrebrown7642]

Видимо, речь о всех случаях, когда c != m по модулю m

[@mistrebrown7642]

Хотя, нет, ерунда получается

[@ВячеславПопов-ф8и]

Борис Викторович ,согласитесь ли Вы с возникшим предположение, что Ферма предложил малую и ВТФ

[@ВячеславПопов-ф8и]

(далее) уловив удивительное свойство разложения (a+b)^ p=(a^p+b^p) - p K ?! Именно такое было началом доказательства ВТФ мною сначала для простых n=p , а потом составных нечётных и чётных степеней . На это потрачено 20 лет поиска и уложилось в 10 страниц

[@Vvv-oi6jd]

Здравствуйте, Борис. Поясните пож., как будет выглядеть в доказательстве МТФ факториал остатков r1...rp-1, при a

[@trushinbv]

Не бывает отрицательных остатков )

[@Vvv-oi6jd]

@@trushinbv Если a=3, p=5. Из каких остатков сложится факториал? Спасибо, что нашли время ответить!

[@Vvv-oi6jd]

Я разобрался. У 3-х будет остаток 3. Все остатки 1,2,3,4.

[@trushinbv]

@@Vvv-oi6jd у 3 остаток 3 у 6 остаток 1 у 9 остаток 4 у 12 остаток 2

[@ЖумагалиевАлишер-с5м]

Для того что бы понять малую теорему Ферма , что нужно знать ?

[@lol-rt5te]

Что такое функция Эйлера, отношение сравнения, простые числа, деление с остатком, кольца вычетов. Думаю этого достаточно

[@kozanuch4405]

остатки и делимость чисел... больше ничего, её можно понять начав смотреть с ролика #034. Я начал смотреть оттуда и кристально понимаю что из чего следует здесь.

[@sergzelin3284]

Все-таки интересно, как строго доказать что сравнение по модулю m можно сократить на множитель, не имеющий общих делителей с m.

[@trushinbv]

А это разве не строго? Если AB делится на C, и A взаимно просто C, то В делится на С. Это следует из основной теоремы арифметики

[@sergzelin3284]

@@trushinbv Не услышал в этом место ролика слов про основную теорему арифметики. Услышал, что "не помогает"... :)

[@almatytelecom1]

сокращать можно если сократить и модуль тоже!!!!

[@trushinbv]

Если, конечно, модуль на это делится )

[@9TailsExar]

6 сравнимо с 2 по модулю 4, но 3 не сравнимо с 1. Зато 3 сравнимо с -1 15 сравнимо с 3 по модулю 6, но 5 и 1 не сравнимо. Зато 5 и -1 сравнимо 20 и 14 сравнимо по модулю 6, но 10 и 7 не сравнимо. Как и 10 с -7 не сравнимо 27 и 15 сравнимы по модулю 12, но 9 и 5 не сравнимы. Как и 9 и -5 не сравнимо мне кажется есть небольшая система. Если сумма чисел дает делимое нацело число, то даже если их нод общего множителя и делителя не 1, то при сокращении общего множителя два числа все еще сравнимы как а и -б. К сожалению не смог подобрать такую пару, где второе число после сокращения общего множителя не было бы 1, а сами числа были бы сравнимы по модулю, подобрать не смог для проверки. Поэтому на системе не настаиваю, но как будто наклевывается что-то. апдейт. Нашел 20 и 12 сравнимы по модулю 8. Убираем четверку, остается 5 и 3. Они не сравнимы по модулю 8. Зато 5 и -3 сравнимы. правило вроде такое: для а*с сравнимое с б*с по модулю р, если а+б делится на р нацело и |а-б|*с тоже, то даже если нод (с, р) больше 1, то а сравнимо с -б по модулю р вроде канает.

[@Toropigeon]

А повторы уроков тоже в платном доступе?

[@trushinbv]

Про какие уроки вы спрашиваете?

[@Toropigeon]

@@trushinbv те, что на фоксфорде

[@trushinbv]

@@Toropigeon, да, но в записи они продаются в разы дешевле, чем стоили, когда курс шёл.

[@kovrigini]

@@trushinbv Когда курс онлайн и можно задавать вопросы, тогда понятно в чем смысл. Если же курс оффлайн, не лучше ли взять хорошую книжку?

[@amikalen1857]

@@kovrigini кто тебе мешает? Бери. Но там то трушин рассказывает, а не какай-то умная книжечка

[@MrPe4KiN96]

genius

[@ИгорьГащук]

Сможет ли кто - нибудь доказать что 25**14 = 1(mod6) Функция Эйлера не имеет значений ф(n) = 14,26,34,38,62,74,.. почему? или 25**14 = 1(mod208)

[@musicsrise]

1) Если внимательно посмотреть на возведение в степень числа с точки зрения его делимости, то получим s = (ab + r)^n, для проверки s ÷ b, дальше можно разложить эту скобку по биному Ньютона и заметить, что ab^n будет делиться на b, и последующие n-1 слагаемых будут делиться на b, тк. содержат множитель b в некоторой степени, тогда на делимость сей суммы будет влиять только последний элемент суммы: r^n. Возвращаясь к твоей задаче, 25 сравнимо с 1 по модулю 6 => 25^k сравнимо с 1^k. (Эйлерова функция не призвана считать 1-ничные остатки чисел). Последний пример аналогичен: 25^2^7= 625^7, 625 сравнимо с 1 по модулю 208: 208*3 = 624 2) Можно посчитать, как ищется функция Эйлера для переменной x: x-1 - (все делители числа x, не включая x. Вернувшись к основной теореме арифметики, можно найти разложение числа на простые множители, и по теореме найти количество делителей: s = p1^a1 * p2^a2 *...* pn^an, тогда количество делителей: d = (a1 + 1)*(a2+1)*...*(an+1) (делители включая само число, а нам необходимы делители без изначального числа, так получим формулу Fe(x) = (x - 1) - (d(x)-1) = x - d(x) (все числа от 1, до x-1 минус делители числа, меньшие самого числа). Так вот у теоремы эйлера есть свойство мультипликативности: F(mn) = F(m) * F(n), у 14, 26, 34, 38 и тд. в разложении на какие-то делители нет таких чисел, чтобы произведение функции от 1-го делителя, на функцию от 2-го получалось именно это число (14, 26 ... и тд.) Ps. Если что - то непонятно, напиши. Про свойство мультипликативности, если честно, узнал, пока отвечал на коммент :)

[@ИгорьГащук]

@@musicsrise Да знаю я и могу доказать, просто прикалываюсь, просто это совсем другая теорема и функция Эйлера здесь ни при чем 25**346 = 1(mod208) или 25**8 = 1(mod208) 21**25 = 1(mod20) И кто знает эту теорему?

[@musicsrise]

@@ИгорьГащук До этого был ролик Трушина об остатках и еще о признаках делимости - из той же оперы

[@ИгорьГащук]

@@musicsrise Малая теорема Ферма здесь не причем 14 - число не простое и теорема Эйлера ф(n) не имеет значение 14 и Трушин здесь ни причем. А вот интересно, кто знает две формулы нахождения пифагоровы троек или только классику z = a^2 + b^2; x = b^2 - a^2; y = 2*a*b и a < b и разной четности, а если a и b - оба числа нечетны?

[@ИгорьГащук]

@@musicsrise Все на много проще 25**14 = 1(mod 24) (Теорема о соседних числах (правда это я ее вывел и так назвал) => 25**14 = 1(mod6 = 24/4 = 6) То есть значения остатка не зависит от значения степени 25**123 = 1(mod 24) ; 25**67 = -1(mod 26) ; 34**234 = 1(mod 33)

[@streetworkout3690]

Борис Трушин почему вы взяли только такие числа a 2a 3a 4a 5a 6a 7a .......(p-1)a , а не a 2a 3a 4a....(p-1)a pa и так далее?

[@krauze8244]

Потому что ap будет иметь нулевой остаток от деления на p, а дальше остатки будут повторяться

[@CallMeMrA]

20:48 а где код ?

[@trushinbv]

какой? )

[@CallMeMrA]

@@trushinbv пригласительный для фоксфорда

[@trushinbv]

Араз Шафиев В описании кек видео есть ссылка

[@ДмитрийЛарин-я1у]

Было бы неплохо сразу приводить примеры в цифрах, а не "буквах", а то просто получается, что смотришь видио на другом языке, не улавливая мысль.

[@ywbc1217]

НА САМОМ ДЕЛЕ ПРАВИЛЬНОО ТАК: СОКРАШАТЬ ВСЕГДА МОЖНО НА МНОЖИТЕЛЬ, КОТОРЫЙ НЕ ИМЕЕТ ОБЩИЙ ДЕЛИТЕЛЬ С m НО СОКРАШАТЬ ТАКЖЕ ИНОГДА МОЖНО И НА МНОЖИТЕЛЬ, КОТОРЫЙ ИМЕЕТ ОБЩИЙ ДЕЛИТЕЛЬ С m ----------------------------- например: c = 5 m = 25 a = 3 b = 28 Борис 3 раза (ТРИ РАЗА !!!!!) в видео говорит, что сокращать можно, НО ТОЛЬКО при условии, что c и m не имеют общего делителя. Это большая неточность!

[@lol-rt5te]

@@ywbc1217 не правильно

[@ywbc1217]

@@lol-rt5te правильно )

[@sergeilyubski852]

Boris. Po povodu delimosti . Gde u menya dyrka ? c = 2, a = 12 , b = 4, m = 4. 2*12 mod 4 = 0. 2 *4 mod 4 = 0. Pravilno ? delim na 2. 12 mod 4 = 0, 4 mod 4 = 0. I 2*12 - 2*4 = 16 delitysa na 4. 12 - 4 = 8 delitsya na 4. T.e. c =2, m = 4 imeyutobstchiy delitel 2. Pravilno ? No pri etom a-b sami po sebe iznachalno prekrasno delyatsya na 4. Tak chto vashe utverzhdenie ne rabotaet. Vidino ne xvataet kakogo to usloviya.

[@trushinbv]

Вы про какое утверждение?

[@sergeilyubski852]

@@trushinbv ac=bc mod m . togda a = b mod n esli HOD ( c, m) = 1 . V moem trivialnom primere c = 2, m = 4 i ochevidno NOD( c, m) != 1 .

[@trushinbv]

@@sergeilyubski852 мы доказали, что если НОД равен 1, то можно сокращать. Никто не утверждал, что что можно ТОЛЬКО если НОД равен 1

[@sergeilyubski852]

@@trushinbv A ok, ponyal. U menya est estcho voprosy pro umnozheniyu. Sformuliruyu. Spasibo.

[@caramba2233]

@@trushinbv kzbin.info/www/bejne/eIusi31opcx7eMk, там вроде можно на их gcd поделить тоже

[@Nutalant]

а что означает #037?

[@trushinbv]

Порядковый номер выпуска

[@_Yes_.]

Лол лол

[@epsilon.sw_]

37 = 12 * 2 + 3 Где 12 = 3 * 4 А 3 + 4 = 7 Отсюда 7 Однако 12 * 2 Посему на втором месте после 3 Иначе 3 * 1 + 12 * 2 Посему 37 А почему в начале 0 Ну Трушин - робот А решеткой у него обозначается десятичная система Хотя ей обычно обозначают шеснадцатиричную Вот например число #037037 которое обычно сокращают до #037 обозначает зеленый цвет Доска у Трушина такого же цвета Что еще раз подтверждает, что Трушин - робот

[@abdullatifbokov14]

А что вообще значит модуль м?

[@trushinbv]

Начните с этого kzbin.info/www/bejne/onnKfpxul5dqd5Y

[@Ал-тайДіЙ]

- это НИКАКОЕ! НЕ! "доказательство" охватывает только ОДНО! из условий , что "а" НЕ делится на "р" и НИКАК!!! НЕ! обращает НИКАКОГО! внимания на второе ГЛАВНОЕ!(для именно- ДОКАЗАТЕЛЬСТВА!) условие...

[@Ал-тайДіЙ]

в этом "доказательстве" - НЕТ!!!! НИКАКОГО! "доказательства"!

[@sergmetlev8559]

Ну и чушь...

[@Алтынбекок]

почему же?

[@უკუნისამდე]

Почему?

[@bogdan7798]

Класс!

[@jenik6210]

Спасибо