2014 dxdy logo

Научный форум dxdy

Математика, Физика, Computer Science, Machine Learning, LaTeX, Механика и Техника, Химия,
Биология и Медицина, Экономика и Финансовая Математика, Гуманитарные науки




 
 Остаток при делении степени двойки на её показатель
Сообщение16.11.2010, 10:39 
Почему $2^{1990}$ даёт именно остаток 1024 при делении на 1990? Это как-то связано с Малой Теоремой Ферма?

 
 
 
 Re: Остаток при делении степени двойки на её показатель
Сообщение16.11.2010, 10:59 
Аватара пользователя
А в чём нетривиальность? Ну, должно же оно давать какой-то остаток.

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

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

 
 
 
 Re: Остаток при делении степени двойки на её показатель
Сообщение16.11.2010, 11:53 
ИСН в сообщении #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.

 
 
 
 Re: Остаток при делении степени двойки на её показатель
Сообщение16.11.2010, 12:32 
Аватара пользователя
Эдак у Вас $2^n-2$ всегда на $n$ поделится :-)

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

 
 
 
 Re: Остаток при делении степени двойки на её показатель
Сообщение16.11.2010, 12:36 
Алгоритм:
Разложить 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.

 
 
 
 Re: Остаток при делении степени двойки на её показатель
Сообщение16.11.2010, 12:53 
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.

Ой, пасибки :oops:

 
 
 
 Re: Остаток при делении степени двойки на её показатель
Сообщение16.11.2010, 13:14 
$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}$

 
 
 
 Re: Остаток при делении степени двойки на её показатель
Сообщение16.11.2010, 15:36 
Аватара пользователя
Пусть $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-й не следует...

 
 
 
 Re: Остаток при делении степени двойки на её показатель
Сообщение16.11.2010, 15:56 
Аватара пользователя
Day в сообщении #375928 писал(а):
остаток от деления степени двойки на саму эту степень - некая степень двойки

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

 
 
 
 Re: Остаток при делении степени двойки на её показатель
Сообщение16.11.2010, 16:01 
Аватара пользователя
ИСН, вы правы!
Посчитал до n=30
2^18 % 18 = 10
2^25 % 25 = 7
2^27 % 27 = 26

 
 
 
 Re: Остаток при делении степени двойки на её показатель
Сообщение16.11.2010, 22:33 
А чем вас сама малая теорема Ферма не устраивает:
$a^{\varphi(n)} = 1 mod n$ если $a$ взаимно просто с $n$.
$\varphi(n)$ - функция Эйлера

 
 
 [ Сообщений: 11 ] 


Powered by phpBB © 2000, 2002, 2005, 2007 phpBB Group