Остаток при делении степени двойки на её показатель

[Xenia1996]

Почему $2^{1990}$ даёт именно остаток 1024 при делении на 1990? Это как-то связано с Малой Теоремой Ферма?

[ИСН]

А в чём нетривиальность? Ну, должно же оно давать какой-то остаток.

-- Вт, 2010-11-16, 12:09 --

Остаток от деления $2^n$ на $n$ - очевидно, для степеней двойки 0, для простых чисел 2 (спасибо малой теореме Ферма, но на этом её роль кончается), для остальных чисел что угодно. Некоторые остатки представляют собой великую редкость, см. topic4786.html

[Xenia1996]

ИСН в сообщении #375836 писал(а):

А в чём нетривиальность? Ну, должно же оно давать какой-то остаток.

-- Вт, 2010-11-16, 12:09 --

Остаток от деления $2^n$ на $n$ - очевидно, для степеней двойки 0, для простых чисел 2 (спасибо малой теореме Ферма, но на этом её роль кончается), для остальных чисел что угодно. Некоторые остатки представляют собой великую редкость, см. topic4786.html

Просто на региональной индийской олимпиаде предлагалась задача: какой остаток даёт $2^{1990}$ при делении на 1990? Честно говоря, я просто угадала ответ. Так как $2^{199}$ даёт остаток 2 при делении на 199, я предположила, что $2^{1990}=(2^{199})^{10}$ будет давать остаток $2^{10}=1024$ при делении на 1990.

[Хорхе]

Эдак у Вас $2^n-2$ всегда на $n$ поделится

Но вообще это случайность, конечно.

[Ales]

Алгоритм:
Разложить 1990 в произведение простых $1990=2*5*199$.
Сократить на 2, осталось $2^{1990-1}$ и $5*199$.
С помощью Малой теоремы Ферма найти остаток от деления числа $2^{1990-1}$ на каждое из этих простых, будет два остатка 2 и 114.
Используя Китайскую теорему об остатках, найти число $z$ до 995, которое имеет те же остатки при делении на эти простые:
$40*5-199=1$, $z+995k=2+5x=114+199y$, $5x-199y=112$, $x=40*112$,
$z=2+5*40*112-995k=22402-995k=402+5*22=512$.
Умножаем на 2, получаем 1024.

[Xenia1996]

Ales в сообщении #375862 писал(а):

Алгоритм:
Разложить 1990 в произведение простых $1990=2*5*199$.
Сократить на 2, осталось $2^{1990-1}$ и $5*199$.
С помощью Малой теоремы Ферма найти остаток от деления числа $2^{1990-1}$ на каждое из этих простых, будет два остатка 2 и 114.
Используя Китайскую теорему об остатках, найти число $z$ до 995, которое имеет те же остатки при делении на эти простые:
$40*5-199=1$, $z+995k=2+5x=114+199y$, $5x-199y=112$, $x=40*112$,
$z=2+5*40*112-995k=22402-995k=402+5*22=512$.
Умножаем на 2, получаем 1024.

Ой, пасибки

[Батороев]

$1990=2\cdot 5\cdot 199$
$\operatorname{lsm} \left((2-1),(5-1),(199-1)\right)=396$
$1990\equiv 10 \pmod {396}$, следовательно:
$2^{1990}\equiv 2^{10}\equiv 1024\pmod {1990}$

[Day]

Пусть $n = p*k$, p - простое
Тогда $2^p=2(mod (p)) (Эйлер)$
$2^p = 2 (mod (p*k))$
$2^n = (2^p)^k = 2^k (mod (n))$
Итак, остаток от деления степени двойки на саму эту степень - некая степень двойки. Ваш результат вполне закономерен, странно было бы, если б получилось 1025

ЗЫ. Кажется, погорячился...3-я строчка из 2-й не следует...

[ИСН]

Day в сообщении #375928 писал(а):

остаток от деления степени двойки на саму эту степень - некая степень двойки

это только если $n>2^k$ (что, впрочем, подходит под наш случай), а так-то что угодно было бы. Остаток 1025 первый раз встречается для $n=1881$.

[Day]

ИСН, вы правы!
Посчитал до n=30
2^18 % 18 = 10
2^25 % 25 = 7
2^27 % 27 = 26

[AlexandreII]

А чем вас сама малая теорема Ферма не устраивает:
$a^{\varphi(n)} = 1 mod n$ если $a$ взаимно просто с $n$.
$\varphi(n)$ - функция Эйлера