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
1055
Для людей, знакомых с арифметикой остатков, очевидно.

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


16/02/13
4179
Владивосток
Ну, как только напишете доказательство, так сразу станет абсолютно очевидным.
Ну, а без доказательства — чуть менее, имхо, очевиден, чем факт $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
1055
Есть такие факты: $((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 ] 

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



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

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


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

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