How do I find the remainder of $4^0+4^1+4^2+4^3+ \cdots + 4^{40}$ divided by 17?

Recently I came across a question,

Find the remainder of $4^0+4^1+4^2+4^3+ \cdots + 4^{40}$ divided by 17?

At first I applied sum of G.P. formula but ended up with the expression $1\cdot \dfrac{4^{41}-1}{4-1}$. I couldn't figure out how to proceed further. Secondly I thought of using the fact $(a+b+\cdots) \pmod {17} = (r_a+r_b\dots) \pmod {17}$ but it is getting more messier.

Please explain in detail. And also mention the formula being used.

• Is the $4^2$ deliberately missing? And are all other exponents less than $40$ supposed to be present? – André Nicolas Aug 7 '15 at 16:52
• In the future, even if you don't remember all the other manipulations, it may be useful to keep in mind that (for example) $4^{40} \bmod 17 = 4\cdot4^{39} \bmod 17 = 4(4^{39} \bmod 17)$. You can extend that chain all the way down to the bottom. – Brian Tung Aug 7 '15 at 17:05
• @AndréNicolas It was a typo. It is a geometric progression with common ratio 4. – user103816 Aug 8 '15 at 5:30
• Two typos, it is still in the title. But then things are simple. sums by groups of $4$ are congruent to $0$, so the sum is congruent to $1$. – André Nicolas Aug 8 '15 at 6:07

HINT:

Observe that for any non-negative integer $a,$ $$1+4+4^2+4^3=(1+4)(1+4^2)\equiv0\pmod{17}$$

$$\implies\sum_{a=m}^n4^{4a}(1+4+4^2+4^3)\equiv0\pmod{17}$$

Here $m=0,n=9$

• So we have to find only $4^{40}/17$'s remainder? – user103816 Aug 8 '15 at 5:43
• Yes, that's correct. – wythagoras Aug 8 '15 at 6:36
• How can we find $(17-1)^{20} \pmod {17}$? My idea is to use $(17-1)^{20}=17f(n)+(-1)^{20}$, where $f(n)$ is some natural number and then use the fact $xN \pm b \pmod N = \pm b \pmod N$. – user103816 Aug 8 '15 at 9:15
• @user103816, True. Do you know mathworld.wolfram.com/Congruence.html ? – lab bhattacharjee Aug 8 '15 at 9:17
• Yes I know that if $a-b$ is divisible by $N$ then $a$ and $b$ leave same remainders when divided by $N$. – user103816 Aug 8 '15 at 9:19

$$\frac{4^{41}-1}{4-1}\equiv \frac{2^{82}-1}{4-1}\equiv \frac{2^2-1}{4-1}\equiv 1\pmod{17}.$$ Fermat's little theorem was used: $2^{16}\equiv 1\pmod{17}$ implies: $$2^{82} = 2^{5\cdot 16+2} = 4\cdot \left(2^{16}\right)^5 \equiv 4\pmod{17}.$$

Another approach. Let $a_n = 4^0+4^1+\ldots+4^n$. Then obviously $a_{n+1}=4a_n+1$, so given $a_n\pmod{17}$, to compute $a_{n+1}\pmod{17}$ is straightforward. $a_0=1$, so our sequence $\pmod{17}$ goes this way: $$1 \to 5 \to 4 \to 0 \to 1 \to 5 \to 4 \to \ldots$$ hence it is $4$-periodic. That implies $a_{40}\equiv a_{0}\equiv 1\pmod{17}$.

• Maybe it should be mentioned that Euler's theorem was used. – orion Aug 7 '15 at 17:41
• @orion: suggestion accepted. – Jack D'Aurizio Aug 7 '15 at 17:44
• @JackD'Aurizio, for a geometric series isnt $|r| < 1$ required? – Amad27 Aug 7 '15 at 17:52
• @Amad27, there are no series involved, this is just a partial sum of geometric sequence: $1 + x + x^2 + \cdots + x^n = \frac{x^{n+1}-1}{x-1}$ which works for any $x\neq 1$. – Ennar Aug 7 '15 at 17:57
• @user103816: Assuming that $c-d$ is an invertible element, that is trivial. – Jack D'Aurizio Aug 8 '15 at 16:58

If you calculate $4^{k}\ (\operatorname{mod}\ 17)$ for some $k$'s, you might quickly notice that the values are periodically $1,4,-1,-4$. This is not coincidence, since $4^4 \equiv 1 \ (\operatorname{mod}\ 17)$, and thus $$4^{4k+l}\equiv 4^{4k}\cdot 4^l \equiv (4^4)^k\cdot 4^l \equiv 4^l \ (\operatorname{mod}\ 17)$$ So, we conclude $$4^{4k+1}+4^{4k+2}+4^{4k+3}+4^{4k+4}\equiv 4 + (-1) + (-4) + 1 \equiv 0 \ (\operatorname{mod}\ 17)$$ and can calculate $$4^0+4^1+4^3+\cdots 4^{40} \equiv (4^0+4^1+4^3+4^4)+\sum_{k=1}^9(4^{4k+1}+4^{4k+2}+4^{4k+3}+4^{4k+4}) \equiv 4^0+4^1+4^3+4^4 \equiv 1 + 4 + (-4) + 1 \equiv 2\ (\operatorname{mod}\ 17)$$ Of course, if $4^2$ is accidentally missing in the question, sum just as easily evaluates to $1$.

• Thank you, your method is quite understandable.. – user103816 Aug 8 '15 at 5:46

Hint: $$4^2 = 16 \equiv -1 \mod 17$$ $$4^4 \equiv (-1)^2 \equiv 1 \mod 17$$

• And what about odd powers of $4$? – user103816 Aug 8 '15 at 5:40
• $4^3 \equiv -1\cdot 4 = -4 \mod 17$ – wythagoras Aug 8 '15 at 6:36