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 ] 

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



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

Сейчас этот форум просматривают: нет зарегистрированных пользователей


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

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