Is the member sum of a subset of $\mathbb{Z}/p\mathbb{Z}$ known (with $g^n \bmod p$)? Is it always $\mod P = 0$?

Question

Let $P$ be a prime and $g$ a value between $2$ and $P$.
Let $M$ be the set of numbers which can be generated with $g$:
$$M = \{g^n\bmod P, \text{ with } 0 < n <P \}$$ If $g$ is a prime root of $P$ all values $1$ to $P-1$ can be generated.
The sum of those would be:
$$S=\sum M = \sum_{n=1}^{P-1} (g^n \bmod P) = \sum_{n=1}^{P-1} n= (P/2)\cdot (P-1)$$

Is there also a formula for values $g$ not a prime root of $P$?
(So for generators $g$ which are only able to generate a subset of $\mathbb{Z}/p\mathbb{Z}$)
Question: What is exact sum of such a subset?

---

Partly solution:
During testing around I noticed one factor of this sum $S$ seems to be $P$.
So $$ S = \sum M = c \cdot P$$ and with this $$ 0 \equiv S \bmod P$$

Is that always the case? EDIT: seems to be the case, see comment from runway44 (edit end)
Any way to calculate this factor $c$?

---

Example: $g=13, P=23$
With $g=13$ only half the numbers out of $\mathbb{Z}/23\mathbb{Z}$ can be generated:
$M = \{13,8,12,18,4,6,9,2,3,16,1\}$
sum $S=\sum M = 92$, which is $4 \cdot P$
Why $4$ times? Any way to compute this factor?

Answer 1

(I observe $S=c\cdot P$ for some integer $c$.) Is that always the case?

Yes. Proof follows.

If $g=P$ then $S=0$. We'll disregard this special case in the following.

The set $M$ has $k$ elements, with $k$ the lowest strictly positive integer with $g^k\equiv1\pmod P$. This $k$ is known as the order of $g$ modulo $P$. This $k$ divides $P-1$. $M$ also is $\{g^n\bmod P, \text{ with } 0 \le n <k \}$, and in this later definition the $g^n\bmod P$ are distinct.

It follows $\displaystyle S=\sum_{n=0}^{k-1}\left(g^n\bmod P\right)$.

Therefore $\displaystyle S\equiv\left(\sum_{n=0}^{k-1}g^n\right)\pmod P$.

$g\ne 1$. Therefore $\displaystyle S\equiv\frac{g^k-1}{g-1}\pmod P$.

It holds $g^k-1\equiv0\pmod P$. Since $P$ is prime and $g\in[2,P]$, $g-1\ne0\pmod P$.

Therefore $S\equiv0\pmod P$. That is $\exists c\in\Bbb Z, S=c\cdot P$

Any way to calculate this factor $c$?

If $k$ is even, then $c=k/2$. Argument: if $k$ is even and $x\in M$, it can be shown that $x'=P-x\in M$. We can pair the elements of $M$ into $k/2$ pairs which each sum to $P$.

If $k$ is odd, $c\approx k/2$ still holds. An heuristic argument is that $S$ is the sum of $k$ terms about haphazardly distributed in $[1,P-1]$, thus about $P/2$ on average. That's the best I can tell.

Notes:

• $c$ depend only on $k$ and $P$ (not $g$), per the fundamental theorem of cyclic groups.
• We can efficiently tell the parity of $k$ from $P$ and $g$: write $P-1$ as $2^\lambda z$ for odd $z$; then $g^z\bmod P=1$ iff $k$ is even (as commented by poncho).
• $k$ can be efficiently found from $P$, $g$, and the factorization of $P-1$.