найти четыре последные цифры

[daogiauvang]

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

[ddn]

daogiauvang писал(а):

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

$(2^{2001^2}+2001)\mod 10000=(2^{2001^2\mod \phi(2^4\cdot 5^4)}+2001)\mod 10000=(2^{(2001-1)^2+2\cdot 2001-1\mod 4000}+2001)\mod 10000=(2^{0+2-1}+2001)\mod 10000=(2+2001)\mod 10000=2003\mod 10000=2003$

[daogiauvang]

ddn писал(а):

daogiauvang писал(а):

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

$(2^{2001^2}+2001)\mod 10000=(2^{2001^2\mod \phi(2^4\cdot 5^4)}+2001)\mod 10000=(2^{(2001-1)^2+2\cdot 2001-1\mod 4000}+2001)\mod 10000=(2^{0+2-1}+2001)\mod 10000=(2+2001)\mod 10000=2003\mod 10000=2003$

Почему Вы выбрали по modulo 4000? Объясните мне детальнее .

[незваный гость]

Малая теорема Ферма: $a^{\varphi(n)} = a \, ({\rm{mod}} \, n)$, где $\varphi(n)$ — функция Эйлера.

[juna]

незваный гость
Только сравнима с единицей.

Добавлено спустя 35 секунд:

Да и ответ неверен.
Правильно 0753

[незваный гость]

Лукавый попутал. Имелось в виду $a^p = a$, для любого $a$. Что и важно в данном случае, поскольку 2 и 10000 не являются взаимно-простыми. А так можно через китайскую теорему об остатках.

[ddn]

Малая теорема Ферма: $a^{\varphi(n)}\mod n=1=a^0$, откуда $a^m\mod n=a^{m\mod \varphi(n)}\mod n$.
$\varphi(10000)=\varphi(2^45^4)=(2-1)(5-1)2^35^3=4000$.
Что и было использовано.

juna писал(а):

Да и ответ неверен.
Правильно 0753

Почему же неверен?

Добавлено спустя 3 минуты 48 секунд:

А, понял. Нет взаимной простоты. Вообще-то, я в начале считал через $5^4$ но потом бросил.

Добавлено спустя 36 минут 57 секунд:

daogiauvang писал(а):

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

$2^{2001^2}+2001\mod 5^4=(2^{2001^2\mod\varphi(5^4)}+2001)\mod 5^4=(2^{2000^2+2\cdot2000+1\mod 500)}+2001)\mod 5^4=(2^1+2001)\mod 625=2003\mod 625=2003-1875=128$
и
$2^{2001^2}+2001\mod 2^4=(2^{(2001^2-2^2)+4}+2000+1)\mod 2^4=(0+2^45^3+1)\mod 2^4=(0+0+1)\mod 2^4=1$

Тогда $2^{2001^2}+2001=5^4m+128=5^4(2^4k+r)+128=10000k+5^4r+128$ и $2^{2001^2}+2001=2^4m'+1=2^4(5^4k'+r')+1=10000k'+2^4r'+1$.
$5^4r+128<10000$ и $2^4r'+1<10000$, откуда $k=k'$ и $5^4r+128=2^4r'+1$, где $0\leqslant r<2^4$ и $0\leqslant r'<5^4$.
Решается только перебором. Возмутительно!
Ответ: $r=1$ и $r'=(625+128-1)/16=39-8=31$, откуда $2^{2001^2}+2001\mod 10000=625\cdot1+128=753$

[juna]

Кстати, если бы нужно было посчитать только две последние цифры, то можно существенно все сократить:
$\forall n,k\in \mathbb N: n^{20k+2}\equiv n^2 \mod 100\to$
$\to 2^{2001}\equiv 2^{21}\mod 100, (2^{21})^{2001}\equiv 2^{21}\equiv 52 \mod 100$

[daogiauvang]

спасибо dnn.
Ответ правилно:0753

[Батороев]

daogiauvang писал(а):

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

$ 2001^2=4004001\equiv 4001\pmod{10000} $
$ (2^{4001}+2001)=(2\times 2^{2\times2\times2\times 2\times 2\times 5\times 5\times 5}+2001)\equiv0753\pmod{10000} $

[незваный гость]

Батороев, поясните, пожалуйста, переход от первой ко второй строке. То есть, я понимаю, что $2^{500} \equiv 9376$ и $9376^n \equiv 9376$, но «под каким научным предлогом»? Как сей факт найти?

[Echo-Off]

незваный гость писал(а):

:evil:
$9376^n \equiv 9376$

$9376^2=87909376\equiv9376\pmod{10000}$, далее по индукции

[незваный гость]

Echo-Off в сообщении #139458 писал(а):

далее по индукции

Я же написал — это понятно. Вопрос, собственно, был — из каких соображений выбирается 500? Потому, что 10000 Батороева выглядят просто среднепотолочной величиной. И работают только из-за 500.

[Батороев]

незваный гость писал(а):

:evil:
Батороев, поясните, пожалуйста, переход от первой ко второй строке. То есть, я понимаю, что $2^{500} \equiv 9376$ и $9376^n \equiv 9376$, но «под каким научным предлогом»? Как сей факт найти?

Уважаемый незваный гость , извините, но у меня нет никакого научного предлога к этому переходу.
Для подобных случаев я использую (может быть, по-шарлатански) степени числа 11.
Т.е. $ 11^{500} = (10 + 1)^{500} = 10^{500}+....+ x*100*1+ 500*10^{1}*1+1 $ (не помню сейчас, какой там полиномиальный к-т на месте $x$ )
и если число без последней единицы будет кратно $10000$, то и четыре последних знака через $500$ степеней будут повторяться, причем и у всех других чисел. Не знаю наверняка, правильный ли способ, но контрпримеры не попадались (может, искал плохо).

незваный гость писал(а):

:evil:

Echo-Off в сообщении #139458 писал(а):

далее по индукции

Я же написал — это понятно. Вопрос, собственно, был — из каких соображений выбирается 500? Потому, что 10000 Батороева выглядят просто среднепотолочной величиной. И работают только из-за 500.

$ 10000 $ здесь использую, исходя из задания в четыре последних разряда, которые и являются остатком по основанию $10000$.

[juna]

незваный гость писал(а):

:evil:
Батороев, поясните, пожалуйста, переход от первой ко второй строке. То есть, я понимаю, что $2^{500} \equiv 9376$ и $9376^n \equiv 9376$, но «под каким научным предлогом»? Как сей факт найти?

Мы это обсуждали здесь. В своем предыдущем посте я не стал рассматривать модули свыше ста. В разделе "Помогите" - это достаточный hint