Найдите три последние цифры числа $$2003^{{2002}^{2001}}$$ задан 16 Фев '14 13:13 parol |
Найти последние три десятичные цифры означает нахождение остатка по модулю 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 falcao у меня так же вышло !!! 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
|
Какими средствами разрешается пользоваться? Можно ли в решении использовать теорему Эйлера?
там из темы деление с остатком
А какой ещё материал из теории чисел освоен к этому моменту? Скажем, сравнения (по заданному модулю) и их свойства разрешено привлекать?
да это можно , хотелось бы увидеть решение по Эйлеру
Внизу уже нет возможности для комментирования, поэтому отвечаю здесь. Согласно определению, сравнения по модулю рассматриваются только для целых чисел. Поэтому дробные числа типа $%\frac{2^{10}}{15}$% использовать в таком качестве нельзя. Я так понимаю, Вы пытаетесь реконструировать какую-то мысль, но какую именно, я не понимаю. Если речь идёт о процедуре, позволяющей по двум остаткам от деления на взаимно простые числа m и n найти остаток от деления на mn, то это описано в учебниках по теории чисел (китайская теорема об остатках; системы сравнений).