I've been given a proof of the following:
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\equiv 1 \mod{(r-1)}$.
I've 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$), whence we have $q-1$ probabilities, and we know that $\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$ and $-e$ $\geq 0$ ; each term $r^{e_i-e}$ and $r^{-e}\equiv1 \mod{(r-1)}$, so that $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}$ and $r^{-e}\equiv1 \mod{(r-1)}$?