sum of integers using order of integers and primitive roots

Question

Sorry for my interruption, I am looking for a solution to this question: Calculate $$\sum_{k=0}^{2001}\left \lfloor \frac{2^k}{2003}\right \rfloor$$ without using computational engines, with $\lfloor x \rfloor$ denoting the largest integer that does not succeed x. I hope you can answer this question. And sorry for my mistakes, English is my second language.

Answer 1

If we write $2^k=2003q_k+r_k$ you are looking for the sum of the $q_k$. Assume for the moment that we know that $2$ is a primitive root $\bmod 2003$. In that case the $r_k$ run through all the numbers from $1$ through $2002$ and we can write $$\sum_{k=0}^{2001}\Big \lfloor \frac{2^k}{2003}\Big \rfloor=\sum_{k=0}^{2001} \frac {2^k-r_k}{2003}=\frac {2^{2002}-1}{2003}-\frac {2002\cdot 2003}{2\cdot 2003}=\frac {2^{2002}-1}{2003}-1001$$ This gives an explicit expression without summation or floor functions, but actually computing it is beyond most of our patience as it will have about $600$ digits.

I don't have an easy way to show $2$ is a primitive root. The order of $2$ must divide $2002=2\cdot7\cdot 11 \cdot 13$ so we can just check whether $2$ to any of $14$ powers is equivalent to $1 \bmod 2003$. You can generate $2^{2^n}$ by repeated squaring and then multiply them, but it will be tedious.

I realized that all that is needed for this argument to work is to show $2^{1001}\equiv -1 \pmod {2003}$, which will be true if $2$ is a primitive root but might be otherwise. With repeated squaring that is more within the range of hand computation, but still tedious.

Answer 2

Solution from a friend of mine: Since $$2^{1001}=-1(mod 2003) $$ then $$ 2^{1001 + i} + 2^i = 0 (mod 2003),$$ thus $$ \left \lfloor{\frac{2^{1001 + i}}{2003}}\right \rfloor + \left \lfloor{\frac{2^{i}}{2003}}\right \rfloor = \frac{2^{1001 + i} + 2^i}{2003} - 1,$$ therefore $$\sum_{k=0}^{2001}\Big \lfloor \frac{2^k}{2003}\Big \rfloor=\frac {2^{2002}-1}{2003}-1001$$