Найти остаток от деления 2²⁰⁰ на 47 | ПРО ЧИСЛА
2023 ж. 3 Қар.
22 849 Рет қаралды
Продолжаем использовать сравнения для решения различных задач. Сегодня нам предстоит найти остаток от деления 2²⁰⁰ на 47.
Лекцию о сравнениях смотрите по ссылке • Сравнения | ПРО ЧИСЛА
Плейлист ПРО ЧИСЛА • ПРО ЧИСЛА
Тут найдете много интересного.
читает Игорь Тиняков
#сравнения #прочисла #теориячисел
Сегодня я весь день сравнивал числа по модулю и находил остатки от деления. И именно в этот день вы выпускаете видео на эту тему! Не перестаю убеждаться в том, что случайности не случайны. Спасибо за ролик!
Пожалуйста!)
Еще не смотрел, но сдается мне нужна малая теорема Ферма.
Красивый подход с малой Т Ферма. Сначала сам решил эту задачу таким образом: выписал первые несколько чисел кратных 47 и старался через возведение в степень/перемножение сравнений/ домножение обеих частей сравнений на степени двойки получать числа вблизи данных.
В следующий раз как раз малая теорема Ферма)
Супер!
Офигенный канал, только сегодня на него наткулся! Очень много полезной информации! Продолжай делать видеоролики, и вскоре догонешь Трушина, Саваатева, Павликова и многих других. Желаю удачи! 🎉 Кстати, недавно такое же задание попалось в олимпиаде Бауманки по математике: Дано четное число N, не оканчивающееся на 0, найти предпоследнюю цифру N в 60 степени
kzhead.info/sun/ksaGXdJ-pZd7fKc/bejne.htmlsi=MgLdU4aQwWbG4LFB тут похожие задачи были. а догонять не будем, пусть как есть, в своем ритме...
Хороший канал! ) Видео попалось в рекомендованных, нисколько не жалею, что посмотрел. Каюсь, про малую т. Ферма я и забыл как-то... Очень хорошо, что предлагаются разные способы решения. Сам люблю решать различные задачи как минимум 2-3 способами. Остальные видео пока не смотрел (планирую), но априори смею предположить, что канал по нетривиальности и степени сложности рассматриваемых задач в чем-то сходен с каналом "Поступашки" ) В отличие от каналов по типу "Этому не учат в школе", где решение зачастую угадываешь почти сразу. Бывает, интересные задачки и там попадаются, но относительно редко.
Есть такой Путеводитель по каналу Элементарная Математика kzhead.info/sun/dN2QnMyPmKmmnJ8/bejne.html, но он малость устарел и доступен только по ссылке, однако все же как-то показывает, что здесь происходит)
Можно проще решить с точки зрения вычислений - не в квадрат возводить, а на 2 умножать (остатки куда проще считать). Зациклится через 23 умножения на 2, далее 200 = 23 * 8 + 16, 16-ое умножение на 2 уже посчитано. Я за минуту справился, хотя считаю плохо
Да, так и нужно. Для степени 2000, а не 200 такой подход явно лучше. Понятно, что остаток - это число от 0 до 46, т.е. максимум за 47 умножений мы выйдем на цикл. А дальше действовать как Вы. А в данном случае 47- простое число, и малая теорема Ферма говорит 2^(47-1)=1 (mod47). И можно даже цикл не искать. Нужно только 2^16 посчитать.
Спасибо
Пожалуйста!)
В наше время такую арифметику не преподавали даже в физматшколе (ну, в моей, по крайней мере), и для меня всегда было неочевидно, что с остатками по модулю можно оперировать как с обычными числами )
Будет интересно если в конечном итоге Вы дойдёте до начальной криптографии. Просто теория чисел хоть и красивая математика, сама по себе, но мало применимая к реальности на первый взгляд. Мне кажется, что практическая сторона окажется хорошим мотиватором для многих зрителей.
да, в этом направлении хотелось бы однажды продолжить)
Ну количество знаков же легко считается, всего-то нужен десятичный логарифм с точностью до трех знаков. 1+[200log2] = 61. Можно еще использовать широкоизвестный факт, что 2^10=1024=10^3*1.024, а затем сделать оценку 1.024^20 < (1+1/40)^20
да, тут kzhead.info/sun/l8aaXciwhaanZpE/bejne.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
Да, но могло бы 2 на степень 2023 например и ещё больше, тогда калькулятор не справится.
@@ivayloivanov5766 предел у того калькулятора 999 степень. Вычислялась секунд 8. Думаю ограничение ввели чтоб сервер не перегружали, а вычисление степени 2023 займет секунд 15-20. Но, в общем-то, я с вами полностью согласен.
@@za_ozero А если не 2, а 3457863684 на степень 3 000? Смысл в том, чтобы показать как элегантно решить задачу, а калькулятор на проверку воспользоваться - почему нет.
Что-то я не понял. Если чётное число возводить в степень, то будет получаться всегда четное число. Если брать остаток от деления на НеЧЕТНОЕ число от Четного, то будет всегда нечетное число. Другими словами, если от четного числа отнимать не четное ответ будет не четным числом. Получили ответ остаток от деления 18 т.е. Четное число. Получается что при возведение 2 в 200-ю степень мы полуяили нечетное число. Вопрос как?
128-47-47=34
Точно, не стой стороны считал. Спасибо.@@elemath
@rytovmisha9524 Было бы за что...
Первое решение заканчивается предположением, что остаток от деления произведения равен произведению остатков от деления множителей, взятому по модулю. А почему это так? С суммой то же утверждение вроде как очевидно, а с произведением не могу понять
Начало про сравнения kzhead.info/sun/ksaGXdJ-pZd7fKc/bejne.html там и свойства
Потрясный канал!) Какую литературу вы бы посоветовали по ТЧ, чтонить широкоохватное, как комбинаторика Виленкина?
Сушкевич весьма доходчиво изложил.
@@elemath Я с Болгарии. Как называется книга, чтобы поискать? Ролик про системы сравнении будет(есть)?
@ivayloivanov5766 Теория чисел. Еще посмотрите K.Rosen Elementary Number Theory and Its Applications. Задачка как раз из этой книги.
@ivayloivanov5766 Сравнения недавно на канале появились. Систем пока не было. Вчера вышла первая часть по линейным сравнениям.
@@elemath вообще-то тяжело найти по тему. Полгода назад искал. Нашел на английском и что-то индийское. Да, и женщина была преподаватель, русскоговорящая. Она и советами помогла, другие попытались, но вне своих примерах не смогли уйти, как-то странно. Короче, сравнения очень интересные, но мало в Ютубе, а наглядно более легче воспринимается. Спасибо за ответы!
легко - 18
Мне было лень думать, поэтому забил степени двойки до 30-ти в ексель и посмотрел периодичность остатков от деления на 47. Получилось 23 (=46/2). Дальше получаем тот же остаток, что и от 2^16, т.е. 18.
15 минут на задачу, которая в уме за 2 минуты решается. Если для объяснения темы - лучше начинать с более простых, для начала - на последнюю цифру числа.
200 гексация 10
Можете ещё придумать задачку на эту тему? Интересно проверить, понял ли сын решение. :)
Найдите остаток от деления 7⁶⁵ на 60.
Найдите остаток от деления 50! на 2⁴⁸. Это по предыдущим упражнениям.
Спасибо большое! 😉
@user-yp1dd4rz8b Пожалуйста!)
5:15 случайно не "-25"? Тогда 47-25=22. Сейчас пятый час ночи, проверять нет желания. Но, если не забуду, то вечером проверю. Не удержался... Проверил остаток от 2^25. Получилось 4. Как ни крути а в итоге остаток от 2^200 18 не выйдет...
Утро вечера мудренее.
Квадрат всегда положителен
А еще надо было Малую Теорему Ферма юзать. 2^(47*4) сравнимо с 2^4
многие задачи на этом канале решаются не ради решения, они используют те методы, которые уже были рассмотрены, а другие, более простые, появляются лишь после решения, дабы показать их преимущество. Так было и здесь. Малая теорема Ферма появляется лишь в конце видео, но кто смотрит до конца...
Теорема: a^(p-1) = 1 mod(p) 2^200 = (2^46)^4 * 2^16 = 2^16 = 18 mod(47) Edit: Вы потом ей и воспользовались. Написал до того как досмотрел.
Только важно помнить что а и р взаимнопростые)
я ничего не понял, это в каком классе дается? я не понимаю что такое мод
Модуль - это делитель. Делим 2 на 47, получаем 0 целых и 2 в остатке. Делим 50 на 47 - получаем 1 целую и 3 в остатке. Целые части в данном контексте нас не интересуют, а работаем лишь с остатками от деления на 47.
kzhead.info/sun/ksaGXdJ-pZd7fKc/bejne.htmlsi=KGzK2u0Ryhij4NqY с этого все начиналось...
Это олимпиадная математика. Класс 8-9й
@arthurmullin7255 если не 6-ой...
Три решения за пятнадцать минут, славно.
Похоже "Малая Теорема Ферма" НЕ верна. Например для a = 2, p = 35, видим, что 2^34 = 17179869184, но при этом 17179869183 не делится на 35. И таких примеров огромное множество...
только вот число 35 не является простым...
@@elemath Ах, Вы правы, я как-то упустил этот момент, Вы сказали в видео "взаимно простых" чисел и я подумал, что это касается любых чисел, которые не делятся друг на друга. А для простых чисел это правило действительно будет соблюдаться всегда. Там очень интересная, но строгая закономерность.
@flamehowk так и есть, только начал с того, что р - простое. В эту субботу вернемся к Малой теореме Ферма и ее обобщению.
@@elemath Честно говоря, я сам вывел эту закономерность. Не знал, что Ферма сделал это намного раньше. Недостатки отсутствия классического образования... С другой стороны разобраться самому намного интереснее, чем просто изучить чье-то решение.
@flamehowk это да, Вы правы.
Ничего подобного я на ютубе ещё не видел! Очень сложно и интересно.
Без бутыля неразберешь
это личное дело каждого отдыхающего...
😂😂😂
Что касается цифр то 2¹⁰=1024 1024=>1000 1000¹⁰=1х30*0 Теперь все это в ² 1х60*0 То есть 1 и 60 нолей 61 цифра
2^200=(2^10)^20, что приблизительно равно 1000^20=(10^3)^20=10^60
А смысл? В Экселе эта формула на раз вбивается, 10 сек ответ есть. Сам подход автора тоже ничему не учит, непонятно в чем смысл разбора таких задач
ты сам тупой да
Задача глупая и бессмысленная по умолчанию. Оперировать такими числами это бред.
Не точно так. Малые числа в криптографии легко пробить. Сломать шифр будет развлечение.
Всегда знал, что """математики""" это сбежавшие пациенты психиатрической клиники. Дядя, ты не халтурь, ты покажи нам как ты возводишь 2 в степень 200. И честно скажи - подобные операции очень важны, и используются в таких-то технологиях, в таких-то отраслях науки и техники. Без этого, ты просто клоун, который может жонглировать сразу 6-9-ю предметами - бесполезное действо, тупо шоу.
Сынок, зачем так-то, а? Комментарии прочитай, может быт поймёшь! Там где-то написано,что это используется в криптографии. Означает в Биткойна, в кредитных картах и так далее.
@@ivayloivanov5766 это ты автору видосика высказывай, чтобы он не забывал проговаривать. Ну и пусть попляшет у доски и таки возведёт 2^200. Впрочем, мы же знаем, что математики в бешенстве от компьютеров, которые вытесняют их нафиг. И скоро они все отправятся в дворники.
А вот с допустим практической точки зрения, зачем надо искать эти остатки?
при занятиях криптографией может пригодиться... или просто для гимнастики ума.
@@elemath Да, про крипту я понимаю, но там это достаточно бесполезно делать тем методом, который Вы предлагаете. Ну, про гимнастику - да, это понятно.
@Observer1973 так и есть, но постепенно будем продвигаться...
вот такие и пишут учебники для 1клашек)))) им то всё очевидно((( а ты сиди и думай: чож автор хотел то?
главное то, что они заставляют Вас думать.
бля, ну и где ответ-то?!