# Thread: find 1+2+2^2 + 2^3 +......+2^219 mod13

.

2. ## Re: find 1+2+2^2 + 2^3 +......+2^219 mod13

1+2+2^2+...+2^219=2^(220)-1. Now 2 has order 12 mod 13; since 220 is 4 mod 12, 2^220 is 2^4 mod 13 or 3. So then your integer is 2 mod 13.

3. ## Re: find 1+2+2^2 + 2^3 +......+2^219 mod13

Hello, dave52!

$\displaystyle \text{Find: }\:N \:=\:1+2+2^2 + 2^3 + \cdots + 2^{219}\text{ (mod 13)}$

We have: .$\displaystyle N \;=\;2^{220}-1$

Consider consecutive powers-of-2 (mod 13).

. . . $\displaystyle \begin{array}{ccccccc}2^0 &\equiv & 1 && 2^7 &\equiv& 11 \\ 2^1 &\equiv&2 && 2^8 &\equiv& 9 \\ 2^2 &\equiv& 4 && 2^9 &\equiv& 5 \\ 2^3 &\equiv& 8 && 2^{10} &\equiv& 10 \\ 2^4 &\equiv& 3 && 2^{11} &\equiv& 7 \\ 2^5 &\equiv& 6 && 2^{12} &\equiv& 1 \\ 2^6 &\equiv& 12 && : && : \end{array}$

We see that: .$\displaystyle 2^{12}\:\equiv\:1\text{ (mod 13)}$

We have: .$\displaystyle 2^{220}-1 \;=\;2^{12(18)+4} - 1$

. . . . . . . . . . . . . . $\displaystyle =\;(2^{12})^{18}\!\cdot\!2^4 - 1$

. . . . . . . . . . . . . . $\displaystyle \equiv\;1^{18}\!\cdot\!16 - 1\text{ (mod 13)}$

. . . . . . . . . . . . . . $\displaystyle \equiv\;15\text{ (mod 13)}$

. . . . . . . . . . . . . . $\displaystyle \equiv\;2\text{ (mod 13)}$