Find the remainder of $\sum_{i=0}^{99} 2^{i^2}$ when dividing by 7 and determine if the quotient is even or odd

Question

I've recently had this problem in an exam and couldn't solve it.

Find the remainder of the following sum when dividing by 7 and determine if the quotient is even or odd:

$$\sum_{i=0}^{99} 2^{i^2}$$

I know the basic modular arithmetic properties but this escapes my capabilities. In our algebra course we've seen congruence, divisibility, division algorithm... how could I approach it?

Answer 1

By Fermat's little theorem $$ 2^{i^2}\!\!\!\pmod{7}=\left\{\begin{array}{ll}\color{green}{1}&\text{if } i\equiv 0\pmod{6}\\\color{blue}{2}&\text{if } i\equiv 1\pmod{6}\\\color{blue}{2}&\text{if } i\equiv 2\pmod{6}\\\color{green}{1}&\text{if } i\equiv 3\pmod{6}\\\color{blue}{2}&\text{if } i\equiv 4\pmod{6}\\\color{blue}{2}&\text{if } i\equiv 5\pmod{6}\\\end{array}\right.$$ hence:

$$ \sum_{i=0}^{99}2^{i^2} \equiv \color{blue}{2\sum_{i=0}^{99}1}-\color{green}{\sum_{k=0}^{33}1} \equiv 2\cdot 100-34 \equiv \color{red}{5}\!\!\pmod{7}.$$

In a similar way $$ 2^{i^2}\!\!\!\pmod{14}=\left\{\begin{array}{ll}\color{green}{1}&\text{if } i\equiv 0\pmod{6}\\\color{blue}{2}&\text{if } i\equiv 1\pmod{6}\\\color{blue}{2}&\text{if } i\equiv 2\pmod{6}\\\color{purple}{8}&\text{if } i\equiv 3\pmod{6}\\\color{blue}{2}&\text{if } i\equiv 4\pmod{6}\\\color{blue}{2}&\text{if } i\equiv 5\pmod{6}\\\end{array}\right.$$

hence:

$$ \sum_{i=0}^{99}2^{i^2}\equiv 2\cdot 100-34+\color{purple}{7\cdot 17} \equiv \color{red}{5}\pmod{14}.$$

Answer 2

$2^{i^2}$ mod 7 is determined by $i^2$ mod 6, hence by $i$ mod 6. That should suffice to sort out the remainder. Now the parity of the quotient depends only on the remainder of the sum mod 14, which you can get from knowing the sum mod 7 and mod 2.

Answer 3

E.g. use

$\sum\limits_{i=0}^{99}2^{i^2}=\sum\limits_{i=0}^{32}(2^{(3i)^2}+2^{(3i+1)^2}+2^{(3i+2)^2})+2^{3(3(33^2))}$

and $2^{3n}=(7+1)^n$ divided by $7$ has the remainder $1$ for any integer $n$.

The rest should be clear.