fixfix
2014 dxdy logo

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

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


Правила форума


Посмотреть правила форума



Начать новую тему Ответить на тему
 
 Насколько это очевидно?
Сообщение04.08.2024, 09:33 
Аватара пользователя


22/11/13
02/04/25
549
Пусть $a(n,k) = 2^k\bmod n$. Насколько очевиден тот факт, что
$$a(n,k) = 1 + \left(\sum\limits_{i=0}^{k-1}a(n,i)\right)\bmod n$$?

 Профиль  
                  
 
 Re: Насколько это очевидно?
Сообщение04.08.2024, 09:51 
Заслуженный участник


07/08/23
1394
Для людей, знакомых с арифметикой остатков, очевидно.

 Профиль  
                  
 
 Re: Насколько это очевидно?
Сообщение04.08.2024, 09:53 
Заслуженный участник


16/02/13
4214
Владивосток
Ну, как только напишете доказательство, так сразу станет абсолютно очевидным.
Ну, а без доказательства — чуть менее, имхо, очевиден, чем факт $2^k=1+\sum\limits_{i=0}^{k-1}2^i$

 Профиль  
                  
 
 Re: Насколько это очевидно?
Сообщение04.08.2024, 10:10 
Аватара пользователя


22/11/13
02/04/25
549
Можно еще упростить:
$$a(n,k)=
\begin{cases}
1,&\text{если $k=0$;}\\
2a(n,k-1),&\text{если $2a(n,k-1)<n$;}\\
2a(n,k-1)-n,&\text{в противном случае.}
\end{cases}$$
При этом я все равно не понимаю, как это работает.

 Профиль  
                  
 
 Re: Насколько это очевидно?
Сообщение04.08.2024, 10:24 
Заслуженный участник


07/08/23
1394
Есть такие факты: $((x \bmod n) + (y \bmod n)) \bmod n = (x + y) \bmod n$, $(x \bmod n) (y \bmod n) \bmod n = x y \bmod n$. Из них и равенства для степеней двойки вроде всё следует.

Кстати, если в правой части у вас по модулю берётся только большая сумма, а $1 +$ отдельно, то это неверно. Контрпример: $n = 4$, $k = 2$, тогда слева будет $0$, а справа $4$.

 Профиль  
                  
Показать сообщения за:  Поле сортировки  
Начать новую тему Ответить на тему  [ Сообщений: 5 ] 

Модераторы: Модераторы Математики, Супермодераторы



Кто сейчас на конференции

Сейчас этот форум просматривают: Without Name


Вы не можете начинать темы
Вы не можете отвечать на сообщения
Вы не можете редактировать свои сообщения
Вы не можете удалять свои сообщения
Вы не можете добавлять вложения

Найти:
Powered by phpBB © 2000, 2002, 2005, 2007 phpBB Group