5
$\begingroup$

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.

$\endgroup$
  • 8
    $\begingroup$ Is the $4^2$ deliberately missing? And are all other exponents less than $40$ supposed to be present? $\endgroup$ – André Nicolas Aug 7 '15 at 16:52
  • $\begingroup$ 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. $\endgroup$ – Brian Tung Aug 7 '15 at 17:05
  • $\begingroup$ @AndréNicolas It was a typo. It is a geometric progression with common ratio 4. $\endgroup$ – user103816 Aug 8 '15 at 5:30
  • $\begingroup$ 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$. $\endgroup$ – André Nicolas Aug 8 '15 at 6:07
4
$\begingroup$

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$

$\endgroup$
  • $\begingroup$ So we have to find only $4^{40}/17$'s remainder? $\endgroup$ – user103816 Aug 8 '15 at 5:43
  • $\begingroup$ Yes, that's correct. $\endgroup$ – wythagoras Aug 8 '15 at 6:36
  • $\begingroup$ 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$. $\endgroup$ – user103816 Aug 8 '15 at 9:15
  • $\begingroup$ @user103816, True. Do you know mathworld.wolfram.com/Congruence.html ? $\endgroup$ – lab bhattacharjee Aug 8 '15 at 9:17
  • $\begingroup$ Yes I know that if $a-b$ is divisible by $N$ then $a$ and $b$ leave same remainders when divided by $N$. $\endgroup$ – user103816 Aug 8 '15 at 9:19
10
$\begingroup$

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

$\endgroup$
  • 1
    $\begingroup$ Maybe it should be mentioned that Euler's theorem was used. $\endgroup$ – orion Aug 7 '15 at 17:41
  • $\begingroup$ @orion: suggestion accepted. $\endgroup$ – Jack D'Aurizio Aug 7 '15 at 17:44
  • $\begingroup$ @JackD'Aurizio, for a geometric series isnt $|r| < 1$ required? $\endgroup$ – Amad27 Aug 7 '15 at 17:52
  • 1
    $\begingroup$ @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$. $\endgroup$ – Ennar Aug 7 '15 at 17:57
  • 1
    $\begingroup$ @user103816: Assuming that $c-d$ is an invertible element, that is trivial. $\endgroup$ – Jack D'Aurizio Aug 8 '15 at 16:58
4
$\begingroup$

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

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

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

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

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.