Задачи

Подскажите, как решать подобные задачи, когда $%a^{b^{c...}}$%, знаю, что для $%a^b$% можно воспользоваться теоремой Эйлера, а тут? (Задачи из 4.1, 4.2, 4.3) (Буду очень рад, если решите по одной из каждого номера или объясните алгоритм решения)

задан 5 Окт '17 1:39

10|600 символов нужно символов осталось
1

Все эти примеры однотипны, поэтому достаточно разобрать 4.1.

Мы будем знать вычет числа 5^k по модулю 11, если узнаем вычет k по модулю ф(11)=10. Случай n=1 даёт 5, а если в показателе что-то есть, то это нечётное число, делящееся на 5. Остаток там равен 5. То есть k=10m+5, по малой теореме Ферма 5^10=11(mod 11). Значит, надо найти 5^5 по модулю 11. Для маленьких значений показателя это ручной счёт: 5^2=25=3, 5^4=3^2=-2, 5^5=-10=1 (mod 11). То есть при n>=2 ответом будет 1.

Можно ещё сказать пару слов про 4.2. При малых n всё ясно. Пусть n достаточно велико, и тогда надо знать вычет "башни" из n-1 тройки по модулю 10. Эта задача сводится к нахождению вычета "башни" из n-2 троек по модулю ф(10)=4. Легко видеть, что 3 в неёчтной степени даёт 3. Тогда по модулю 10 имеем 3^3=7. И на последнем шаге считаем 3^7 mod 11. Это даёт 9, так как 3^5=243=1 (mod 11).

Исключения n=1 и n=2 дают 3 и 5, а при n>=3 будут остатки 9.

Общая стратегия такова, что от задачи по модулю n мы переходим к однотипной задаче по модулю ф(n), затем ф(ф(n)), и так далее. Итерации дают всё меньшие и меньшие числа, и рано или поздно они дадут 1, а по модулю 1 всё понятно. Потом идём "сверху вниз".

Можно обратить внимание на 4.4, где ф(19)=18, и к степеням 9 теорема Эйлера не будет применима. Но по модулю 9 остаток 0, а по модулю 2 он равен 1, откуда китайская теорема об остатках даёт значение 9 по модулю 18.

ссылка

отвечен 5 Окт '17 2:50

Я разобрал подпункты 4.3, а в предыдущих случаях идея примерно та же. Для a^b mod n заменяем a на остаток по модулю n, и b на остаток по модулю ф(n), если a взаимно просто с n.

(5 Окт '17 2:52) falcao

Спасибо огромное.

(5 Окт '17 2:58) Williams Wol...
10|600 символов нужно символов осталось
Ваш ответ

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

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

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

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

отмечен:

×3,709

задан
5 Окт '17 1:39

показан
332 раза

обновлен
5 Окт '17 2:58

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

по почте:

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

по RSS:

Ответы

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

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