Насколько это очевидно?

[kthxbye]

Пусть $a(n,k) = 2^k\bmod n$. Насколько очевиден тот факт, что

$$a(n,k) = 1 + \left(\sum\limits_{i=0}^{k-1}a(n,i)\right)\bmod n$$

?

[dgwuqtj]

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

[iifat]

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

[kthxbye]

Можно еще упростить:

$$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}$$

При этом я все равно не понимаю, как это работает.

[dgwuqtj]

Есть такие факты: $((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$.