Найти остаток от деления 2²⁰⁰ на 47 | ПРО ЧИСЛА 

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

Еще не смотрел, но сдается мне нужна малая теорема Ферма.

Красивый подход с малой Т Ферма. Сначала сам решил эту задачу таким образом: выписал первые несколько чисел кратных 47 и старался через возведение в степень/перемножение сравнений/ домножение обеих частей сравнений на степени двойки получать числа вблизи данных.

Супер!

Хороший канал! ) Видео попалось в рекомендованных, нисколько не жалею, что посмотрел. Каюсь, про малую т. Ферма я и забыл как-то... Очень хорошо, что предлагаются разные способы решения. Сам люблю решать различные задачи как минимум 2-3 способами. Остальные видео пока не смотрел (планирую), но априори смею предположить, что канал по нетривиальности и степени сложности рассматриваемых задач в чем-то сходен с каналом "Поступашки" ) В отличие от каналов по типу "Этому не учат в школе", где решение зачастую угадываешь почти сразу. Бывает, интересные задачки и там попадаются, но относительно редко.

Офигенный канал, только сегодня на него наткулся! Очень много полезной информации! Продолжай делать видеоролики, и вскоре догонешь Трушина, Саваатева, Павликова и многих других. Желаю удачи! 🎉 Кстати, недавно такое же задание попалось в олимпиаде Бауманки по математике: Дано четное число N, не оканчивающееся на 0, найти предпоследнюю цифру N в 60 степени

Можно проще решить с точки зрения вычислений - не в квадрат возводить, а на 2 умножать (остатки куда проще считать). Зациклится через 23 умножения на 2, далее 200 = 23 * 8 + 16, 16-ое умножение на 2 уже посчитано. Я за минуту справился, хотя считаю плохо

Будет интересно если в конечном итоге Вы дойдёте до начальной криптографии. Просто теория чисел хоть и красивая математика, сама по себе, но мало применимая к реальности на первый взгляд. Мне кажется, что практическая сторона окажется хорошим мотиватором для многих зрителей.

Спасибо

Ну количество знаков же легко считается, всего-то нужен десятичный логарифм с точностью до трех знаков. 1+[200log2] = 61. Можно еще использовать широкоизвестный факт, что 2^10=1024=10^3*1.024, а затем сделать оценку 1.024^20 < (1+1/40)^20

В наше время такую арифметику не преподавали даже в физматшколе (ну, в моей, по крайней мере), и для меня всегда было неочевидно, что с остатками по модулю можно оперировать как с обычными числами )

Интересно, что если даже мы возьмем отриц остаток, то след все равно можно будет посчитать так же

Огромное спасибо за материал!

Сколько десятичных знаков будет у 2^200=(2^10)^20≈(10³)^20=10^60 Или по другому. Количество десятичных знаков любого числа это целая часть от выражения плюс 1 lg(2^200)=200•lg 2≈200 • 0.301=60.2 Ответ: 61

Спасибо! Очень красиво.

Прекрасное знание математики! Видимо, это необходимо при программировании и создании новых вычислителей. , это, как играющий на флейте в метро, прекрасно, но ни для всех. Ролик просмотрел без звука, вывод, может быть неполноценным.

Что-то я не понял. Если чётное число возводить в степень, то будет получаться всегда четное число. Если брать остаток от деления на НеЧЕТНОЕ число от Четного, то будет всегда нечетное число. Другими словами, если от четного числа отнимать не четное ответ будет не четным числом. Получили ответ остаток от деления 18 т.е. Четное число. Получается что при возведение 2 в 200-ю степень мы полуяили нечетное число. Вопрос как?

Вначале находим, что 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

Можете ещё придумать задачку на эту тему? Интересно проверить, понял ли сын решение. :)

Три решения за пятнадцать минут, славно.

Ничего подобного я на ютубе ещё не видел! Очень сложно и интересно.

Мне было лень думать, поэтому забил степени двойки до 30-ти в ексель и посмотрел периодичность остатков от деления на 47. Получилось 23 (=46/2). Дальше получаем тот же остаток, что и от 2^16, т.е. 18.

200 гексация 10

А еще надо было Малую Теорему Ферма юзать. 2^(47*4) сравнимо с 2^4

5:15 случайно не "-25"? Тогда 47-25=22. Сейчас пятый час ночи, проверять нет желания. Но, если не забуду, то вечером проверю. Не удержался... Проверил остаток от 2^25. Получилось 4. Как ни крути а в итоге остаток от 2^200 18 не выйдет...

Теорема: a^(p-1) = 1 mod(p) 2^200 = (2^46)^4 * 2^16 = 2^16 = 18 mod(47) Edit: Вы потом ей и воспользовались. Написал до того как досмотрел.

легко - 18

15 минут на задачу, которая в уме за 2 минуты решается. Если для объяснения темы - лучше начинать с более простых, для начала - на последнюю цифру числа.

я ничего не понял, это в каком классе дается? я не понимаю что такое мод

Похоже "Малая Теорема Ферма" НЕ верна. Например для a = 2, p = 35, видим, что 2^34 = 17179869184, но при этом 17179869183 не делится на 35. И таких примеров огромное множество...

Без бутыля неразберешь

Что касается цифр то 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-ю предметами - бесполезное действо, тупо шоу.

Задача глупая и бессмысленная по умолчанию. Оперировать такими числами это бред.

А вот с допустим практической точки зрения, зачем надо искать эти остатки?

вот такие и пишут учебники для 1клашек)))) им то всё очевидно((( а ты сиди и думай: чож автор хотел то?

бля, ну и где ответ-то?!