На днях попалась такая задача. Найти остаток от деления числа 6^{3^{1000}} на 176. Я получил ответ, но хочется свериться..

задан 9 Июн 1:52

изменен 9 Июн 1:52

1

176 = 2^4*11 по КТО получаем систему:
x = 0 mod 16
x = 6^3^1000 mod 11
Функция эйлера от 11 равна 10, поэтому рассмотрим:
3^1000 mod 10 = 1
получаем
x = 0 mod 16
x = 6 mod 11 -> x = 160
Ответ: 160

(9 Июн 2:01) Williams Wol...

Спасибо большое! получил такой же ответ, только решение гораздо больше!

(9 Июн 2:06) cs_puma

А как вы решали?

(9 Июн 2:10) Williams Wol...

Я разложил данное число на произведение 2^3^1000 и 3^3^1000. Далее 2^3^1000 * 3^3^1000=х(mod 176)

Так как левая 176=16*11 и левая часть делится на 11, то х=16у

2^(3^1000-4) * 3^3^1000=у(mod 11)

А дальше искал остатки от деления чисел 2^(3^1000-4) и 3^3^1000 на 11 через теорему Ферма. Но Ваше решение гораздо короче!

(9 Июн 2:14) cs_puma
10|600 символов нужно символов осталось
Знаете, кто может ответить? Поделитесь вопросом в Twitter или ВКонтакте.

Ваш ответ

Если вы не нашли ответ, задайте вопрос.

Здравствуйте

Математика - это совместно редактируемый форум вопросов и ответов для начинающих и опытных математиков, с особенным акцентом на компьютерные науки.

Присоединяйтесь!

отмечен:

×3

задан
9 Июн 1:52

показан
69 раз

обновлен
9 Июн 2:15

Отслеживать вопрос

по почте:

Зарегистрировавшись, вы сможете подписаться на любые обновления

по RSS:

Ответы

Ответы и Комментарии

Дизайн сайта/логотип © «Сеть Знаний». Контент распространяется под лицензией cc by-sa 3.0 с обязательным указанием авторства.
Рейтинг@Mail.ru