0
1

Найдите три последние цифры числа $$2003^{{2002}^{2001}}$$

задан 16 Фев '14 13:13

Какими средствами разрешается пользоваться? Можно ли в решении использовать теорему Эйлера?

(16 Фев '14 13:25) falcao

там из темы деление с остатком

(16 Фев '14 13:26) parol

А какой ещё материал из теории чисел освоен к этому моменту? Скажем, сравнения (по заданному модулю) и их свойства разрешено привлекать?

(16 Фев '14 13:58) falcao

да это можно , хотелось бы увидеть решение по Эйлеру

(16 Фев '14 14:14) parol

Внизу уже нет возможности для комментирования, поэтому отвечаю здесь. Согласно определению, сравнения по модулю рассматриваются только для целых чисел. Поэтому дробные числа типа $%\frac{2^{10}}{15}$% использовать в таком качестве нельзя. Я так понимаю, Вы пытаетесь реконструировать какую-то мысль, но какую именно, я не понимаю. Если речь идёт о процедуре, позволяющей по двум остаткам от деления на взаимно простые числа m и n найти остаток от деления на mn, то это описано в учебниках по теории чисел (китайская теорема об остатках; системы сравнений).

(17 Фев '14 15:53) falcao
10|600 символов нужно символов осталось
2

Найти последние три десятичные цифры означает нахождение остатка по модулю 1000. Это значит, что 2003 можно заменить на 3 в силу свойств сравнений, которые можно возводить в натуральную степень.

Поскольку $%\varphi(1000)=\varphi(2^3)\varphi(5^3)=(2^3-2^2)(5^3-5^2)=400$%, из теоремы Эйлера следует, что $%3^{400}\equiv1\pmod{10^3}$%. Следует установить, какой остаток от деления на 400 даёт показатель степени, то есть число $%2002^{2001}$%. Если он равен $%r$%, то показатель степени имеет вид $%400q+r$%, и тогда $%3^{400q+r}\equiv(3^{400})^q3^r\equiv3^r\pmod{10^3}$%, и задача сводится к нахождению последних трёх цифр числа $%3^r$%.

Заметим, что $%2002\equiv2\pmod{400}$%, поэтому достаточно найти остаток от деления на 400 для числа $%2^{2001}$%. Здесь теорему Эйлера напрямую уже не применить, так как 400 и 2 не взаимно просты. Однако $%400=2^4\cdot5^2$%, поэтому можно отдельно найти остатки от деления на 16 и на 25. В первом случае ответ очевиден: остаток равен нулю, так как $%2^{2001}$% заведомо делится на $%2^4$%. А остаток от деления на 25 можно найти уже по теореме Эйлера, пользуясь тем, что $%\varphi(25)=20$%. Тогда $%2^{20}\equiv1\pmod{25}$%, откуда $%2^{2001}=(2^{20})^{100}\cdot2\equiv2\pmod{25}$%.

Таким образом, число $%2^{2001}$% при делении на 16 даёт в остатке 0, а при делении на 25 даёт в остатке 2. Из этих данных, в силу китайской теоремы об остатках, однозначно определяется остаток от деления на $%400=16\cdot25$%. Нас интересует число вида $%16m$%, где $%m$% целое, такое что $%16m\equiv2\pmod{25}$%. Сокращаем сравнение на 2, затем домножаем на 3, откуда $%-m\equiv24m\equiv3\pmod{25}$%. Тем самым, $%m\equiv22\pmod{25}$%, и $%16m\equiv16\cdot22\equiv352\pmod{400}$%.

Исходная задача в итоге свелась к нахождению последних трёх цифр числа $%3^{352}$%. Здесь пока что не очень удобно проводить вычисления, поэтому имеет смысл заметить, что $%10^3=2^3\cdot5^3$%, сводя задачу к нахождению остатков от деления на 8 и на 125.

Первая из задач решается совсем легко, потому что $%3^{352}\equiv9^{176}\equiv1\pmod8$% с учётом того, что 9 сравнимо с 1. Остаток от деления на 8, таким образом, равен 1. Для нахождения остатка от деления на 125 достаточно заметить, что $%\varphi(125)=100$%, и тогда мы можем перейти к числу $%3^{52}$%, "списывая" в показателе число, кратное значению функции Эйлера. Чтобы не возводить число в такую высокую степень, можно заметить, что речь идёт о числе $%(3^4)^{13}$%, то есть $%81^{13}$%. Здесь уже остаток вычисляется сравнительно легко при помощи последовательных возведений в квадрат: $%81^2\equiv6561\equiv61\pmod{125}$%; $%81^4\equiv61^2\equiv3721\equiv96\pmod{125}$%; $%81^8\equiv96^2\equiv9216\equiv91\pmod{125}$%. Отсюда $%81^{13}\equiv81^8\cdot81^4\equiv81^1\equiv91\cdot96\cdot81\equiv111\cdot81\equiv116\pmod{125}$%.

Теперь осталось найти число вида $%125n+116$%, дающее остаток 1 от деления на 8. Рассматривая числа указанной арифметической прогрессии, видим, что число 241 обладает нужным свойством. Таким образом, $%3^{352}\equiv241\pmod{10^3}$%, то есть искомыми тремя последними цифрами будут 241.

ссылка

отвечен 16 Фев '14 15:08

у меня так же вышло !!! 241 только чуть чуть по другому решал

(16 Фев '14 15:14) parol

Тут можно было решать по-разному. Например, сразу перейти к остаткам от деления на 8 и на 125. Но при этом какие-то вычисления всё равно требуются. По крайней мере, я не знаю, как без них обойтись. А какой способ Вы применяли?

(16 Фев '14 15:21) falcao

я все так почти сделал но только в конечном итоге перешел на такое 2^17=y (mod 25) это y=22, затем нужно умножить на 16 , что бы мод равнялся 400 , откуда 16*22=352 дальше понятно все

(16 Фев '14 17:18) parol

это я дальше продолжал операцию с начало было 2^157=y (mod 25) 2^17=y (mod 25)

(16 Фев '14 17:42) parol

У меня это разъяснено в том месте, где рассматривается число 16m. Предлагаю просто перечитать -- там все действия со сравнениями подробно описаны. На собственно теорему я при этом не ссылаюсь -- она только упоминается.

(16 Фев '14 21:07) falcao

Это тоже разъяснено в решении. Здесь речь идёт о показателе степени, то есть о числе $%2002^{2001}$%. По модулю 25, мы заменяем 2002 на 2, а у 2001 берём остаток от деления на $%\phi(25)=20$%. Получается $%2^1=2$%.

(17 Фев '14 9:53) falcao

Придётся повторить ещё раз то, что у меня в явном виде написано. Нам надо найти остаток от деления на 400 числа $%2002^{2001}$% (или $%2^{2001}$%, что то же самое. Я замечаю, что сразу применить теорему Эйлера нельзя, и представляю 400 как произведение $%16\cdot25$%. Отдельно нахожу остатки интересующего меня числа при делении на 16 и на 25. Первый из них равен 0, второй равен 2 -- это уже выяснили. Теперь, поскольку число делится на 16, я его записываю в виде 16m, и именно у него остаток от деления на 25 равен 2.

(17 Фев '14 11:27) falcao

следовательно по вашей логике следует к примеру такой $$2^{10}=4 (mod 15)$$ $$2^{10}=0 (mod 2)$$

$$2^{10}=2m$$ $$\frac{2^{10}}{15}=\frac{2m}{15} (mod 30)$$

а вот если $$2^{10}=4 (mod 15)$$ $$2^{10}=1 (mod 3)$$ по мод 45 уже по другому будет да?

(17 Фев '14 12:33) parol
показано 5 из 8 показать еще 3
10|600 символов нужно символов осталось
Ваш ответ

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

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

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

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

отмечен:

×4,987
×4,004
×547

задан
16 Фев '14 13:13

показан
6208 раз

обновлен
17 Фев '14 15:53

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

по почте:

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

по RSS:

Ответы

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

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