Последние три цифры числа 2^10000

[chifa]

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

Предполагается использовать в решении теорию групп, но как ее применить? Быть может подскажете, на чем тут можно сыграть?

[Профессор Снэйп]

Рассмотрите группу $\mathbb{Z}_{125}^\ast$.

[Sasha2]

А если без теории групп.
Так пойдет $2^{100000}=(2^{8})^{12500}=256^{1250}$
Произведение любого чила чисел, заканчивающихся на 6, есть такое же число.

[Профессор Снэйп]

Sasha2 в сообщении #271980 писал(а):

А если без теории групп.
Так пойдет $2^{100000}=(2^{8})^{12500}=256^{1250}$
Произведение любого чила чисел, заканчивающихся на 6, есть такое же число.

Так ему надо три последних цифры, а не одну.

[chifa]

Sasha2, спасибо, но так мы найдем лишь одну последнюю цифру..
Профессор Снэйп, почему берем именно $\mathbb{Z}_{1000}$, а не скажем $\mathbb{Z}_{10000}$?
А, уже $\mathbb{Z}_{125}^*$

[Sasha2]

Тогда пардон, был невнимателен, извиняюсь.

-- Ср дек 16, 2009 13:33:49 --

В таком случае, если не получится с теорией групп, попробуйте, например, показать, что произведение любых двух чисел, заканчивающихся на 376, также заканчивается на эти три цифры

[Профессор Снэйп]

chifa в сообщении #271983 писал(а):

Sasha2, спасибо, но так мы найдем лишь одну последнюю цифру..
Профессор Снэйп, почему берем именно $\mathbb{Z}_{1000}$, а не скажем $\mathbb{Z}_{10000}$?
А, уже $\mathbb{Z}_{125}^*$

Нам нужно лишь три последние цифры, поэтому $1000 = 5^3 \cdot 2^3$, $5^3 = 125$.
Порядок $\mathbb{Z}_{125}^\ast$ равен $\varphi(125) = 125 - 25 = 100$. Значит, $2^{100}$ имеет остаток $1$ при делении на $125$ и $2^{10000}$ тоже.

Но нам, на самом деле, надо найти, чему равно $2^{97}$ в группе $\mathbb{Z}^\ast_{125}$. То есть вычислить $2^{-3}$ в этой группе.

-- Ср дек 16, 2009 15:58:51 --

Смотрим сначала по модулю $5$: $2^4 = 16 = 5 \cdot 3 + 1$.
Далее, $2^{96} = (2^4)^{24} = (15 + 1)^{24} = \sum_{i=0}^{24} C_{24}^i 15^i = 1 + 24 \cdot 15 + (24 \cdot 23)/2 \cdot 15^2 + 125 \cdot k$ для некоторого натурального $k$. Получаем, что остаток от деления $2^{96}$ на $125$ равен $86$. Ну а остаток от деления $2^{97}$ на $125$ равен $47$.

Получаем $2^{9997} = 125 \cdot m + 47$ и $2^{10000} = 1000 \cdot m + 376$.

Гм, $376$ --- действительно правильный ответ. Браво, Sasha2!

[TOTAL]

chifa в сообщении #271974 писал(а):

Предполагается использовать в решении теорию групп, но как ее применить?

а) приводите любое правильное утверждение из теории групп (чтобы отвязались)
б) по $\mod 1000$ имеем $8\cdot2^{7k}=8\cdot3^{k}$ (индукция), $3^{100}=(10-1)^{50}=1$
с) $2^{10000}=16 \cdot 2^{7 \cdot 1428}=16 \cdot 3^{1428}=16 \cdot 3^{28}=16 \cdot (10-1)^{14}=16 \cdot(-39)=376$

[Профессор Снэйп]

TOTAL в сообщении #271998 писал(а):

а) приводите любое правильное утверждение из теории групп (чтобы отвязались)

Ну тогда уж после этого лучше

б) $2^{100} = 1267650600228229401496703205376 \equiv 376\, (\mathrm{mod}\, 1000)$.
в) $376^2 = 141376 \equiv 376\, (\mathrm{mod}\, 1000)$.

P. S. То решение, которое я предложил выше, использует теорию групп, так что можно его.

[Профессор Снэйп]

Кстати, вопрос по ходу. Как мультипликативная группа $\mathbb{Z}_n^\ast$ обратимых элементов кольца $\mathbb{Z}_n$ раскладывается в прямую сумму циклических подгрупп, порядки которых являются степенями простых чисел? Набор порядков этих подгрупп и их порождающие как-то можно вычислить по $n$?

Если $n$ --- простое, то тут всё понятно: $\mathbb{Z}_n^\ast$ --- цикличекая группа порядка $n-1$ и если $n-1 = p_1^{\alpha_1} \ldots p_k^{\alpha_k}$, то $\mathbb{Z}_n^\ast \cong \mathbb{Z}_{p_1^{\alpha_1}} \oplus \ldots \oplus {Z}_{p_k^{\alpha_k}}$. А если $n$ не простое, что тогда? Вот, к примеру, $\mathbb{Z}_{1000}^\ast$ или $\mathbb{Z}_{125}^\ast$ как разложить?

[Cave]

Профессор Снэйп
Вы тему по этому вопросу меньше года назад заводили: topic18728.html

[Профессор Снэйп]

(Оффтоп)

Да, совсем рассеянный стал.

Ладно ещё прошлогоднюю тему не вспомнил. Сегодня вот кредитку в банкомате забыл...

[bot]

(Оффтоп)

Я тоже забывал. Пошёл в банк, заявил. Через неделю вернули - ту же самую, банкомат их взад глотает. Вот если Вы ещё забыли в каком банкомате забыли, то ... м-м-м, не знаю, наверно тоже вернут, только дольше ждать придётся. Деньги, забытые взять, банкомат тоже глотает, а возвращает ли на счёт? Не знаю - забывать не пробовал.

[Профессор Снэйп]

(Оффтоп)

bot в сообщении #272328 писал(а):

Деньги, забытые взять, банкомат тоже глотает, а возвращает ли на счёт? Не знаю - забывать не пробовал.

Я, блин, пробовал в прошлом году. Нет, на счёт не возвращают.

Там такая система. Приходишь в банк, пишешь заявление. Потом ждёшь, когда банкомат вскроют и посчитают там деньги. Если есть лишние, то их тебе возвращают, согласно заявлению. Я как услышал про эту систему, решил не заморачиваться. Рублей 700 снимал, решил, что не стоит ради этого связываться с бюрократией.

[chifa]

Хотелось бы вернуться к этой теме.
Профессор Снэйп в своем решении чрез теорию групп писал, что $2^{100}~mod~125 = 1$. Это возможно, только если $\mathbb{Z}_{125}^* = (2)$. А как доказать, что любой элемент этой группы равен $2^n~mod~125$, причем $0 \le n \le 99$?