# 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$?

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 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?

• Prove sum of primitive roots congruent to μ(p−1)(modp) – kelalaka Jan 1 at 23:00
• @ kelalaka ty, learned something new. The linked question is similar but could not figure out yet how to use the Moebius function for my question. – J. Doe Jan 1 at 23:54
• You seem to have answered the main question by yourself. Have you thought about posting your own answer – conchild Jan 2 at 11:24
• @conchild: me? I still could not manage to formulate an answer. In linked page its the sum of primitive roots and not all values. There is no product of two factors. Its a sum of those. Can't see any way to get the value $4$ for my example. – J. Doe Jan 2 at 18:10
• The sum $S=\sum g^n$ is invariant under multiplication-by-$g$, i.e. $gS=S$, so if $g\ne 1$ then we can multiply $(g-1)S=0$ by $(g-1)^{-1}$ to get $S=0$. Or you can use the (finite) geometric sum formula for $\sum_{n=0}^{m-1}g^n$ to get $(g^m-1)/(g-1)$, which is $0$ since $g^m=1$, where $m$ is the order of $g$ (i.e. the least whole number $m$ for which $g^m$ is $1$, in which case $1,g,\cdots,g^{m-1}$ is all powers of $g$ listed exactly once). – runway44 Jan 2 at 20:05

(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 , 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$$.
• ($k$ can also be a product of those primes found with factorization, I left this over to shorten the question) – J. Doe Jan 3 at 9:39
• So is it known there is no exact answer for odd $k$? Those kind of $k$ would be the interesting one or to be exact if $k$ is a prime as well. – J. Doe Jan 3 at 9:41
• @J.Doe: I do not know if there is a fast method to find $c$ from $k$ and $P$ with certainty for odd $k$, and if the factorisation of $P-1$ helps. That might be a question for math.SE, perhaps MathOverflow. – fgrieu Jan 3 at 10:05
• You don't need to know the factorization of $P-1$ to determine whether $k$ is even or odd; if we denote $z = (P-1)/2^\lambda$ odd (with $\lambda$ being the integer that makes $z$ an odd integer), then if $g^z = 1$, then $k$ is odd, otherwise, it is even. – poncho Jan 3 at 14:40
• @poncho: I'll put that in the answer. My second blatant steal from you today! – fgrieu Jan 3 at 14:50