Регистрация    Вход    Форум    Поиск    FAQ   alexlarin.net

Список форумов » Решение задач




 Страница 1 из 1 [ Сообщений: 7 ] 



Автор Сообщение
 Заголовок сообщения: Остаток от деления
 Сообщение Добавлено: 08 июн 2018, 23:52 
Не в сети
Аватар пользователя

Зарегистрирован: 08 май 2015, 03:53
Сообщений: 1625
Откуда: Москва
На днях попалась такая задача.
Найти остаток от деления числа `6^(3^1000)` на `176`.
Я получил ответ, но хочется свериться..
Подробности:
`160`


Вернуться наверх 
 Заголовок сообщения: Re: Остаток от деления
 Сообщение Добавлено: 09 июн 2018, 02:02 
Не в сети
Аватар пользователя

Зарегистрирован: 09 апр 2011, 14:49
Сообщений: 6791
Откуда: Москва
Kirill Kolokolcev писал(а):
На днях попалась такая задача.
Найти остаток от деления числа `6^(3^1000)` на `176`.
Я получил ответ, но хочется свериться..
Подробности:
`160`

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`.

_________________
Никуда не тороплюсь!


Вернуться наверх 
 Заголовок сообщения: Re: Остаток от деления
 Сообщение Добавлено: 09 июн 2018, 02:38 
Не в сети
Аватар пользователя

Зарегистрирован: 08 май 2015, 03:53
Сообщений: 1625
Откуда: Москва
OlG писал(а):
Kirill Kolokolcev писал(а):
На днях попалась такая задача.
Найти остаток от деления числа `6^(3^1000)` на `176`.
Я получил ответ, но хочется свериться..
Подробности:
`160`

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!


Вернуться наверх 
 Заголовок сообщения: 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$.


Вернуться наверх 
 Заголовок сообщения: Re: Остаток от деления
 Сообщение Добавлено: 12 июн 2018, 12:38 
Не в сети

Зарегистрирован: 16 фев 2011, 14:13
Сообщений: 1940
А я вообще смысла подобных задач не понимаю.

Для человека, снабженного мало-мальской теорией, это простое упражнение, правда отягощенное вычислительными сложностями, такого же рода, как и при устном счете с большими числами.

Человек, ничего не знающий, но соображающий, скорее всего догадается о цикличности, после чего тоже все решит, только чуть более сложно и нерегулярно.

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

Все лучше, чем "обучать" им рецептурно, в духе `a^b` - одна задача, `a^(b^c)` - другая и.т.д. Тем более, что на любом мат.форуме полно таких рецептурно-обученных, которые не в состоянии сделать следующий логический шаг и решить "задачу, которую не проходили".


Вернуться наверх 
 Заголовок сообщения: Re: Остаток от деления
 Сообщение Добавлено: 12 июн 2018, 15:21 
Не в сети

Зарегистрирован: 14 фев 2012, 19:11
Сообщений: 466
alex123 писал(а):
Все лучше, чем "обучать" им рецептурно, в духе `a^b` - одна задача, `a^(b^c)` - другая и.т.д.

Я бы обучал общим подходам к подобным ситуациям (бинарный алгоритм, цикличность, "склеивание" остатков по разным модулям). Само собой, это никакие не задачи, это упражнения на умение пользоваться стандартными средствами типа малой теоремы Ферма. Неплохо подходит для экзамена в качестве проверки на вшивость (вот завтра у меня как раз экзамен, и что-то подобное можно будет использовать для фильтрации троечников).


Вернуться наверх 
 Заголовок сообщения: Re: Остаток от деления
 Сообщение Добавлено: 12 июн 2018, 19:12 
Не в сети

Зарегистрирован: 16 фев 2011, 14:13
Сообщений: 1940
nnosipov писал(а):
alex123 писал(а):
Все лучше, чем "обучать" им рецептурно, в духе `a^b` - одна задача, `a^(b^c)` - другая и.т.д.

Я бы обучал общим подходам к подобным ситуациям


Я бы тоже.

Но найдется немало учителей и преподавателей, которые устроят рецептурное безумие :(((


Вернуться наверх 
Показать сообщения за:  Сортировать по:  
 
 Страница 1 из 1 [ Сообщений: 7 ] 





Кто сейчас на форуме

Сейчас этот форум просматривают: нет зарегистрированных пользователей и гости: 17

 
 

 
Вы не можете начинать темы
Вы не можете отвечать на сообщения
Вы не можете редактировать свои сообщения
Вы не можете удалять свои сообщения
Вы не можете добавлять вложения

Найти:
Перейти: