find 1+2+2^2 + 2^3 +......+2^219 mod13

**dave52** · January 31st 2013, 03:41 PM

.

**johng** · January 31st 2013, 09:30 PM

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.

**Soroban** · January 31st 2013, 09:34 PM

Hello, dave52!

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

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

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

. . . $\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: . $2^{12}\:\equiv\:1\text{ (mod 13)}$

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

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

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

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

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

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

LinkBack

Thread Tools

Display

find 1+2+2^2 + 2^3 +......+2^219 mod13

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

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

Similar Math Help Forum Discussions

Find if function is increasing or decreasing (Find the derivative)

Find an Equation of the Tangent Line to the parabola at the given point and find....

Given 3 points, find the area of the triangle/find the volume of the parallelepiped

How to find the find local max, min and inflection points from an integral?

Have dv/dx need to find dx/dt ? (have velocity w/ respect displace - find Accel?)

Search Tags