Автор |
Сообщение |
Kirill Kolokolcev
|
Заголовок сообщения: Остаток от деления Добавлено: 08 июн 2018, 23:52 |
|
Зарегистрирован: 08 май 2015, 03:53 Сообщений: 1625 Откуда: Москва
|
На днях попалась такая задача. Найти остаток от деления числа `6^(3^1000)` на `176`. Я получил ответ, но хочется свериться..
|
|
|
|
|
|
|
OlG
|
Заголовок сообщения: Re: Остаток от деления Добавлено: 09 июн 2018, 02:02 |
|
Зарегистрирован: 09 апр 2011, 14:49 Сообщений: 6791 Откуда: Москва
|
Kirill Kolokolcev писал(а): На днях попалась такая задача. Найти остаток от деления числа `6^(3^1000)` на `176`. Я получил ответ, но хочется свериться.. 1. а) `3^(3^1000) equiv 3` mod `176`. б) `3^1000-4 equiv 7` mod `10`. в) `2^(3^1000-4) equiv 2^7 equiv 7` mod `11`. г) `6^(3^1000) equiv 3*7*16 equiv 160` mod `176`.
_________________ Никуда не тороплюсь!
|
|
|
|
|
Kirill Kolokolcev
|
Заголовок сообщения: Re: Остаток от деления Добавлено: 09 июн 2018, 02:38 |
|
Зарегистрирован: 08 май 2015, 03:53 Сообщений: 1625 Откуда: Москва
|
OlG писал(а): Kirill Kolokolcev писал(а): На днях попалась такая задача. Найти остаток от деления числа `6^(3^1000)` на `176`. Я получил ответ, но хочется свериться.. 1. а) `3^(3^1000) equiv 3` mod `176`. б) `3^1000-4 equiv 7` mod `10`. в) `2^(3^1000-4) equiv 2^7 equiv 7` mod `11`. г) `6^(3^1000) equiv 3*7*16 equiv 160` mod `176`. Все так же, спасибо, OlG!
|
|
|
|
|
nnosipov
|
Заголовок сообщения: Re: Остаток от деления Добавлено: 09 июн 2018, 17:19 |
|
Зарегистрирован: 14 фев 2012, 19:11 Сообщений: 466
|
Kirill Kolokolcev писал(а): Я получил ответ, но хочется свериться.. А в чем проблема, если речь идет о проверке именно ответа? В любой системе компьютерной алгебры Вы увидите правильный ответ практически мгновенно. Что касается решения, то оно легко проделывается в уме. Надо разложить $176$ в произведение $16$ и $11$. По модулю $16$ наша степень равна нулю (очевидно), а по модулю $11$ она равна $6$ (малая теорема Ферма плюс очевидный факт, что $3^{1000}$ оканчивается на $1$). Какое же число делится на $16$, а при делении на $11$ дает в остатке $6$? Очевидно, $160$.
|
|
|
|
|
alex123
|
Заголовок сообщения: Re: Остаток от деления Добавлено: 12 июн 2018, 12:38 |
|
Зарегистрирован: 16 фев 2011, 14:13 Сообщений: 1940
|
А я вообще смысла подобных задач не понимаю.
Для человека, снабженного мало-мальской теорией, это простое упражнение, правда отягощенное вычислительными сложностями, такого же рода, как и при устном счете с большими числами.
Человек, ничего не знающий, но соображающий, скорее всего догадается о цикличности, после чего тоже все решит, только чуть более сложно и нерегулярно.
Может оставить подобные "задачи" мат.пакетам? А человеку только то, что имеет устное решение, в обход регулярной процедуры?
Все лучше, чем "обучать" им рецептурно, в духе `a^b` - одна задача, `a^(b^c)` - другая и.т.д. Тем более, что на любом мат.форуме полно таких рецептурно-обученных, которые не в состоянии сделать следующий логический шаг и решить "задачу, которую не проходили".
|
|
|
|
|
nnosipov
|
Заголовок сообщения: Re: Остаток от деления Добавлено: 12 июн 2018, 15:21 |
|
Зарегистрирован: 14 фев 2012, 19:11 Сообщений: 466
|
alex123 писал(а): Все лучше, чем "обучать" им рецептурно, в духе `a^b` - одна задача, `a^(b^c)` - другая и.т.д. Я бы обучал общим подходам к подобным ситуациям (бинарный алгоритм, цикличность, "склеивание" остатков по разным модулям). Само собой, это никакие не задачи, это упражнения на умение пользоваться стандартными средствами типа малой теоремы Ферма. Неплохо подходит для экзамена в качестве проверки на вшивость (вот завтра у меня как раз экзамен, и что-то подобное можно будет использовать для фильтрации троечников).
|
|
|
|
|
alex123
|
Заголовок сообщения: Re: Остаток от деления Добавлено: 12 июн 2018, 19:12 |
|
Зарегистрирован: 16 фев 2011, 14:13 Сообщений: 1940
|
nnosipov писал(а): alex123 писал(а): Все лучше, чем "обучать" им рецептурно, в духе `a^b` - одна задача, `a^(b^c)` - другая и.т.д. Я бы обучал общим подходам к подобным ситуациям Я бы тоже. Но найдется немало учителей и преподавателей, которые устроят рецептурное безумие (
|
|
|
|
|
|
|
|