What is $(7^{2005}-1)/6 \pmod {1000}$? What is $$\frac{7^{2005}-1}{6} \quad(\operatorname{mod} 1000)\:?$$
My approach:
Since $7^{\phi(1000)}=7^{400}=1 \bmod 1000, 7^{2000}$ also is $1 \bmod 1000$.
So, if you write $7^{2000}$ as $1000x+1$ for some integer $x$, then we are trying to $((1000x+1)\cdot(7^5)-1)/6 = (16807000x + 16806)/6 \pmod {1000}$.
Obviously, this must be an integer, so $x=3y$ for some $y$. Then, we are trying to find $16807000\cdot 3y/6+2801 \pmod {1000} = 500y+801 \pmod {1000}$. However, this value can be $301$ or $801$, and I am not sure how to find which one is correct.
Any help is appreciated!
 A: By geometric sum formula we have
$$\frac{7^{2005}-1}{6} = \frac{7^{2005}-1}{7-1} = 1+7+7^2+\dots+7^{2004}$$
The sequence $1,7,7^2,\dots$ has period $20 $ modulo $1000$ (since $7^{20} \equiv 1 \pmod{1000}$).
$$1+7+7^2+\dots+7^{2004} \equiv 100(1+\dots+7^{19})+1+7+7^2+7^3+7^4 \equiv 100\cdot 0+801\equiv 801 \pmod{1000} $$
A: We must multiply the modulus by $\,6\,$ to balance the division by $6$, i.e.
$\qquad 6\mid a \,\Rightarrow\,  a/6 \bmod 1000 = (a \bmod 6000)/6\ $ by the mod Distributive Law
$6000\!=\! 2^4\cdot 3\cdot 5^3$  whose totients $2^3,2,100\mid 2000\,$ so $\,\color{#c00}{7^{2000}\!\equiv 1}\bmod 2^4,3,5^3$ so also mod $6000,\,$ so $\bmod 6000\!:\ a\equiv 7^5 \color{#c00}{7^{2000}}-1 \equiv 7^5-1\equiv4806,\,$ so $\bmod 1000\!:\ a/6\equiv 4806/6 \equiv 801$.
A: You can distinguish between the two possibilities you found by starting modulo $2000$:
because the Carmichael function of $2000$ is $100$, $7^{2000}\equiv(7^{100})^{20}\equiv1\bmod2000$,
so $7^{2005}\equiv7^5\equiv807\bmod 2000$.
Therefore, $7^{2005}-1\equiv806\bmod2000$.
Therefore, $\dfrac{7^{2005}-1}2\equiv403\bmod1000$.
Therefore, $\dfrac{7^{2005}-1}6\equiv403\times3^{-1}\bmod{1000}.$
In general, if $n=3k-1$ then $3^{-1}\equiv k\pmod n$,
and if $n=3k+1$ then $3^{-1}\equiv -k\pmod n$,
so  $3^{-1}\equiv-333\equiv667\bmod{1000}$.
Therefore, $\dfrac{7^{2005}-1}6\equiv403\times667\equiv801\bmod1000$.
A: Just to give a different approach, calculating mod $2000$ and using the fact that
$$3^{2000}=(1-10)^{1000}=1-1000\cdot10+\cdots\equiv1\mod2000$$
we have
$$\begin{align}
7^{2005}-1&=-1-(3-10)^{2005}\\
&\equiv-1-3^{2005}+2005\cdot3^{2004}\cdot10-{2005\choose2}3^{2003}\cdot10^2+{2005\choose3}3^{2002}\cdot10^3\\
&\equiv-1-3^5+5\cdot3^4\cdot10-{5\choose2}3^3\cdot100+{5\choose3}3^2\cdot1000\\
&\equiv-1-243+4050-27000+90000\\
&\equiv-244+50-1000\\
&=-1194\mod2000
\end{align}$$
and thus
$${7^{2005}-1\over6}\equiv{-1194\over6}=-199\equiv801\mod1000$$
A: If $k$ and $n$ are not co-prime, you have to be very careful when dividing by $k\bmod n$ $-$ there may be more than one answer, as you saw. So $806/6\bmod 1000$ is not well-defined, because both $6\cdot 301$ and $6\cdot 801$ are equal to $806\bmod 1000$.
But in this case the problem is well-defined, because the expression $\dfrac{7^{2005}-1}{6}$ is an integer. So we can calculate it before reducing $\bmod 1000$. hgmath's answer shows one way to do this (and Raffaele's answer doesn't).
