Найти остаток от деления 2²⁰⁰ на 47 | ПРО ЧИСЛА
Продолжаем использовать сравнения для решения различных задач. Сегодня нам предстоит найти остаток от деления 2²⁰⁰ на 47.
Лекцию о сравнениях смотрите по ссылке • Сравнения | ПРО ЧИСЛА
Плейлист ПРО ЧИСЛА • ПРО ЧИСЛА
Тут найдете много интересного.
читает Игорь Тиняков
#сравнения #прочисла #теориячисел
Пікірлер: 98
Сегодня я весь день сравнивал числа по модулю и находил остатки от деления. И именно в этот день вы выпускаете видео на эту тему! Не перестаю убеждаться в том, что случайности не случайны. Спасибо за ролик!
@elemath
8 ай бұрын
Пожалуйста!)
Еще не смотрел, но сдается мне нужна малая теорема Ферма.
Супер!
Красивый подход с малой Т Ферма. Сначала сам решил эту задачу таким образом: выписал первые несколько чисел кратных 47 и старался через возведение в степень/перемножение сравнений/ домножение обеих частей сравнений на степени двойки получать числа вблизи данных.
@elemath
8 ай бұрын
В следующий раз как раз малая теорема Ферма)
Хороший канал! ) Видео попалось в рекомендованных, нисколько не жалею, что посмотрел. Каюсь, про малую т. Ферма я и забыл как-то... Очень хорошо, что предлагаются разные способы решения. Сам люблю решать различные задачи как минимум 2-3 способами. Остальные видео пока не смотрел (планирую), но априори смею предположить, что канал по нетривиальности и степени сложности рассматриваемых задач в чем-то сходен с каналом "Поступашки" ) В отличие от каналов по типу "Этому не учат в школе", где решение зачастую угадываешь почти сразу. Бывает, интересные задачки и там попадаются, но относительно редко.
@elemath
7 ай бұрын
Есть такой Путеводитель по каналу Элементарная Математика kzread.info/dash/bejne/c62LzsqQkdrWmco.html, но он малость устарел и доступен только по ссылке, однако все же как-то показывает, что здесь происходит)
Спасибо
@elemath
2 ай бұрын
Пожалуйста!)
Офигенный канал, только сегодня на него наткулся! Очень много полезной информации! Продолжай делать видеоролики, и вскоре догонешь Трушина, Саваатева, Павликова и многих других. Желаю удачи! 🎉 Кстати, недавно такое же задание попалось в олимпиаде Бауманки по математике: Дано четное число N, не оканчивающееся на 0, найти предпоследнюю цифру N в 60 степени
@elemath
8 ай бұрын
kzread.info/dash/bejne/kZaBj9B_nsiredI.htmlsi=MgLdU4aQwWbG4LFB тут похожие задачи были. а догонять не будем, пусть как есть, в своем ритме...
Можно проще решить с точки зрения вычислений - не в квадрат возводить, а на 2 умножать (остатки куда проще считать). Зациклится через 23 умножения на 2, далее 200 = 23 * 8 + 16, 16-ое умножение на 2 уже посчитано. Я за минуту справился, хотя считаю плохо
@MaximusU76
7 ай бұрын
Да, так и нужно. Для степени 2000, а не 200 такой подход явно лучше. Понятно, что остаток - это число от 0 до 46, т.е. максимум за 47 умножений мы выйдем на цикл. А дальше действовать как Вы. А в данном случае 47- простое число, и малая теорема Ферма говорит 2^(47-1)=1 (mod47). И можно даже цикл не искать. Нужно только 2^16 посчитать.
Огромное спасибо за материал!
@elemath
7 ай бұрын
Пожалуйста!)
Будет интересно если в конечном итоге Вы дойдёте до начальной криптографии. Просто теория чисел хоть и красивая математика, сама по себе, но мало применимая к реальности на первый взгляд. Мне кажется, что практическая сторона окажется хорошим мотиватором для многих зрителей.
@elemath
8 ай бұрын
да, в этом направлении хотелось бы однажды продолжить)
Спасибо! Очень красиво.
@elemath
7 ай бұрын
Пожалуйста!)
Ну количество знаков же легко считается, всего-то нужен десятичный логарифм с точностью до трех знаков. 1+[200log2] = 61. Можно еще использовать широкоизвестный факт, что 2^10=1024=10^3*1.024, а затем сделать оценку 1.024^20 < (1+1/40)^20
@elemath
7 ай бұрын
да, тут kzread.info/dash/bejne/lpaVj8axftfXY7w.htmlsi=R1Ms44hywEsOwj9B этим занимались.
В наше время такую арифметику не преподавали даже в физматшколе (ну, в моей, по крайней мере), и для меня всегда было неочевидно, что с остатками по модулю можно оперировать как с обычными числами )
Интересно, что если даже мы возьмем отриц остаток, то след все равно можно будет посчитать так же
Сколько десятичных знаков будет у 2^200=(2^10)^20≈(10³)^20=10^60 Или по другому. Количество десятичных знаков любого числа это целая часть от выражения плюс 1 lg(2^200)=200•lg 2≈200 • 0.301=60.2 Ответ: 61
Прекрасное знание математики! Видимо, это необходимо при программировании и создании новых вычислителей. , это, как играющий на флейте в метро, прекрасно, но ни для всех. Ролик просмотрел без звука, вывод, может быть неполноценным.
Вначале находим, что 2^(46x)%47 = 1 (очев); затем, что 2^184%47 = 1 (следует из первого), затем, что 2^200%47 = 2^(184 + 16)%47 = 2^16 % 47. Это уже считается и калькулятором, и написанным на питухоне за минуту алгоритмом, и банально устным счётом + бумажкой =)
Я калькулятор больших чисел нашел и он выдал ответ. Само число вот 1,606,938,044,258,990,275,541,962,092,341,162,602,522,202,993,782,792,835,301,376 Ответ тоже 18
@ivayloivanov5766
7 ай бұрын
Да, но могло бы 2 на степень 2023 например и ещё больше, тогда калькулятор не справится.
@za_ozero
7 ай бұрын
@@ivayloivanov5766 предел у того калькулятора 999 степень. Вычислялась секунд 8. Думаю ограничение ввели чтоб сервер не перегружали, а вычисление степени 2023 займет секунд 15-20. Но, в общем-то, я с вами полностью согласен.
@ivayloivanov5766
7 ай бұрын
@@za_ozero А если не 2, а 3457863684 на степень 3 000? Смысл в том, чтобы показать как элегантно решить задачу, а калькулятор на проверку воспользоваться - почему нет.
200 гексация 10
15 минут на задачу, которая в уме за 2 минуты решается. Если для объяснения темы - лучше начинать с более простых, для начала - на последнюю цифру числа.
Мне было лень думать, поэтому забил степени двойки до 30-ти в ексель и посмотрел периодичность остатков от деления на 47. Получилось 23 (=46/2). Дальше получаем тот же остаток, что и от 2^16, т.е. 18.
Первое решение заканчивается предположением, что остаток от деления произведения равен произведению остатков от деления множителей, взятому по модулю. А почему это так? С суммой то же утверждение вроде как очевидно, а с произведением не могу понять
@elemath
7 ай бұрын
Начало про сравнения kzread.info/dash/bejne/kZaBj9B_nsiredI.html там и свойства
легко - 18
Что-то я не понял. Если чётное число возводить в степень, то будет получаться всегда четное число. Если брать остаток от деления на НеЧЕТНОЕ число от Четного, то будет всегда нечетное число. Другими словами, если от четного числа отнимать не четное ответ будет не четным числом. Получили ответ остаток от деления 18 т.е. Четное число. Получается что при возведение 2 в 200-ю степень мы полуяили нечетное число. Вопрос как?
@elemath
7 ай бұрын
128-47-47=34
@rytovmisha9524
7 ай бұрын
Точно, не стой стороны считал. Спасибо.@@elemath
@elemath
7 ай бұрын
@rytovmisha9524 Было бы за что...
Теорема: a^(p-1) = 1 mod(p) 2^200 = (2^46)^4 * 2^16 = 2^16 = 18 mod(47) Edit: Вы потом ей и воспользовались. Написал до того как досмотрел.
@northlion1421
7 ай бұрын
Только важно помнить что а и р взаимнопростые)
Потрясный канал!) Какую литературу вы бы посоветовали по ТЧ, чтонить широкоохватное, как комбинаторика Виленкина?
@elemath
7 ай бұрын
Сушкевич весьма доходчиво изложил.
@ivayloivanov5766
7 ай бұрын
@@elemath Я с Болгарии. Как называется книга, чтобы поискать? Ролик про системы сравнении будет(есть)?
@elemath
7 ай бұрын
@ivayloivanov5766 Теория чисел. Еще посмотрите K.Rosen Elementary Number Theory and Its Applications. Задачка как раз из этой книги.
@elemath
7 ай бұрын
@ivayloivanov5766 Сравнения недавно на канале появились. Систем пока не было. Вчера вышла первая часть по линейным сравнениям.
@ivayloivanov5766
7 ай бұрын
@@elemath вообще-то тяжело найти по тему. Полгода назад искал. Нашел на английском и что-то индийское. Да, и женщина была преподаватель, русскоговорящая. Она и советами помогла, другие попытались, но вне своих примерах не смогли уйти, как-то странно. Короче, сравнения очень интересные, но мало в Ютубе, а наглядно более легче воспринимается. Спасибо за ответы!
Можете ещё придумать задачку на эту тему? Интересно проверить, понял ли сын решение. :)
@elemath
7 ай бұрын
Найдите остаток от деления 7⁶⁵ на 60.
@elemath
7 ай бұрын
Найдите остаток от деления 50! на 2⁴⁸. Это по предыдущим упражнениям.
@user-yp1dd4rz8b
7 ай бұрын
Спасибо большое! 😉
@elemath
7 ай бұрын
@user-yp1dd4rz8b Пожалуйста!)
А еще надо было Малую Теорему Ферма юзать. 2^(47*4) сравнимо с 2^4
@elemath
8 ай бұрын
многие задачи на этом канале решаются не ради решения, они используют те методы, которые уже были рассмотрены, а другие, более простые, появляются лишь после решения, дабы показать их преимущество. Так было и здесь. Малая теорема Ферма появляется лишь в конце видео, но кто смотрит до конца...
Три решения за пятнадцать минут, славно.
Ничего подобного я на ютубе ещё не видел! Очень сложно и интересно.
5:15 случайно не "-25"? Тогда 47-25=22. Сейчас пятый час ночи, проверять нет желания. Но, если не забуду, то вечером проверю. Не удержался... Проверил остаток от 2^25. Получилось 4. Как ни крути а в итоге остаток от 2^200 18 не выйдет...
@elemath
7 ай бұрын
Утро вечера мудренее.
@user-ig8de5jf6h
7 ай бұрын
Квадрат всегда положителен
Похоже "Малая Теорема Ферма" НЕ верна. Например для a = 2, p = 35, видим, что 2^34 = 17179869184, но при этом 17179869183 не делится на 35. И таких примеров огромное множество...
@elemath
7 ай бұрын
только вот число 35 не является простым...
@flamehowk
7 ай бұрын
@@elemath Ах, Вы правы, я как-то упустил этот момент, Вы сказали в видео "взаимно простых" чисел и я подумал, что это касается любых чисел, которые не делятся друг на друга. А для простых чисел это правило действительно будет соблюдаться всегда. Там очень интересная, но строгая закономерность.
@elemath
7 ай бұрын
@flamehowk так и есть, только начал с того, что р - простое. В эту субботу вернемся к Малой теореме Ферма и ее обобщению.
@flamehowk
7 ай бұрын
@@elemath Честно говоря, я сам вывел эту закономерность. Не знал, что Ферма сделал это намного раньше. Недостатки отсутствия классического образования... С другой стороны разобраться самому намного интереснее, чем просто изучить чье-то решение.
@elemath
7 ай бұрын
@flamehowk это да, Вы правы.
Что касается цифр то 2¹⁰=1024 1024=>1000 1000¹⁰=1х30*0 Теперь все это в ² 1х60*0 То есть 1 и 60 нолей 61 цифра
я ничего не понял, это в каком классе дается? я не понимаю что такое мод
@Sergueiss
8 ай бұрын
Модуль - это делитель. Делим 2 на 47, получаем 0 целых и 2 в остатке. Делим 50 на 47 - получаем 1 целую и 3 в остатке. Целые части в данном контексте нас не интересуют, а работаем лишь с остатками от деления на 47.
@elemath
8 ай бұрын
kzread.info/dash/bejne/kZaBj9B_nsiredI.htmlsi=KGzK2u0Ryhij4NqY с этого все начиналось...
@arthurmullin7255
7 ай бұрын
Это олимпиадная математика. Класс 8-9й
@elemath
7 ай бұрын
@arthurmullin7255 если не 6-ой...
2^200=(2^10)^20, что приблизительно равно 1000^20=(10^3)^20=10^60
Без бутыля неразберешь
@elemath
7 ай бұрын
это личное дело каждого отдыхающего...
@ivayloivanov5766
7 ай бұрын
😂😂😂
А смысл? В Экселе эта формула на раз вбивается, 10 сек ответ есть. Сам подход автора тоже ничему не учит, непонятно в чем смысл разбора таких задач
@user-pi8ke6dp7r
Ай бұрын
ты сам тупой да
Всегда знал, что """математики""" это сбежавшие пациенты психиатрической клиники. Дядя, ты не халтурь, ты покажи нам как ты возводишь 2 в степень 200. И честно скажи - подобные операции очень важны, и используются в таких-то технологиях, в таких-то отраслях науки и техники. Без этого, ты просто клоун, который может жонглировать сразу 6-9-ю предметами - бесполезное действо, тупо шоу.
@ivayloivanov5766
7 ай бұрын
Сынок, зачем так-то, а? Комментарии прочитай, может быт поймёшь! Там где-то написано,что это используется в криптографии. Означает в Биткойна, в кредитных картах и так далее.
@GerryFolf
7 ай бұрын
@@ivayloivanov5766 это ты автору видосика высказывай, чтобы он не забывал проговаривать. Ну и пусть попляшет у доски и таки возведёт 2^200. Впрочем, мы же знаем, что математики в бешенстве от компьютеров, которые вытесняют их нафиг. И скоро они все отправятся в дворники.
Задача глупая и бессмысленная по умолчанию. Оперировать такими числами это бред.
@ivayloivanov5766
7 ай бұрын
Не точно так. Малые числа в криптографии легко пробить. Сломать шифр будет развлечение.
А вот с допустим практической точки зрения, зачем надо искать эти остатки?
@elemath
7 ай бұрын
при занятиях криптографией может пригодиться... или просто для гимнастики ума.
@Observer1973
7 ай бұрын
@@elemath Да, про крипту я понимаю, но там это достаточно бесполезно делать тем методом, который Вы предлагаете. Ну, про гимнастику - да, это понятно.
@elemath
7 ай бұрын
@Observer1973 так и есть, но постепенно будем продвигаться...
вот такие и пишут учебники для 1клашек)))) им то всё очевидно((( а ты сиди и думай: чож автор хотел то?
@elemath
7 ай бұрын
главное то, что они заставляют Вас думать.
бля, ну и где ответ-то?!