# How many code words if average code length equals entropy

I've been given a proof to show:

If $q\geq2$ then there is a source $S$ with $q$ symbols, and an instantaneous$r$-ary code $C$ satisfying $L(C)=H_r(S)$, if and only if $q\equiv1 \mod{(r-1)}$.

I've only looked at the proof in one direction, but I'm having a hard time making sense of it. I understand that if $L(C)=H_r(S)$ then every $p_i$ is in the form of r to the power of some negative integer (i.e. $p_i=r^{e_i}$, where $e_i$ is less than or equal to zero).

This tells me that the $\sum\limits_{i=1}^q p_i=1=\sum\limits_{i=1}^q r^{e_i}$.

In the proof I have been given the next step is to remove the smallest probability (i.e. the r with the smallest $e_i=e$), then we now have $q-1$ probabilities and we know that the $\sum\limits_{i=1}^q r^{e_i-e}=r^{-e}$. This all makes sense to me. I would think the next part of the proof would go on to show that q-1 is a multiple of r-1, but I honestly don't follow the rest, which is shown below:

"so if $e$= min $e_i$, then $\sum\limits_{i=1}^{q}r^{e_i-e}=r^{-e}$ with $e_i-e$,$-e$ $\geq 0$ ; each term $r^{e_i-e},r^{-e}\equiv1 \mod{(r-1)}$, so $q\equiv1 \mod{(r-1)}$."

Can someone please explain why knowing $\sum\limits_{i=1}^{q}r^{e_i-e}=r^{-e}$ automatically implies that each term $r^{e_i-e},r^{-e}\equiv1 \mod{(r-1)}$?

-
For $n\ge 0$, $r^n\equiv1\mod{(r-1)}$ always, right? For $n=0,1$, it's obvious; for $n\ge 2$, write $r^n=((r-1)+1)^n$ and expand using binomial theorem. Every term except the last contains $r-1$. –  Ashok Oct 14 '13 at 7:39