Finding a module for the series $2^{i}$ from 0 to 219

Question

How can I compute this:

$\{ \sum 2^{i}$ for $i \in [0, 219] \} \pmod{13}$

I tried to manipulate the series by using the root principle to find the number of elements divisible by every prime $\leq 13$. However, I failed.

Is there any way to compute this without doing an excessive amount of calculations? I assume there is a way to factorize it so you can find the modules of each factor and make it simpler.

Answer 1

First of all, note that $\sum\limits_{i=0}^{219}2^i=2^{220}-1$.

Now, let's calculate $2^{220}\bmod13$.

Since $\gcd(13,2)=1$, the "cycle" of $2^n\bmod{13}$ consists of $12$ elements:

• $1$
• $2$
• $4$
• $8$
• $3$
• $6$
• $12$
• $11$
• $9$
• $5$
• $10$
• $7$

Therefore, $2^{220}\bmod{13}=2^{220\bmod{12}}\bmod{13}=2^{4}\bmod{13}=3$.

Therefore, $2^{220}-1\bmod{13}=2$.