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?

  • 1
    $\begingroup$ Prove sum of primitive roots congruent to μ(p−1)(modp) $\endgroup$
    – kelalaka
    Jan 1, 2020 at 23:00
  • $\begingroup$ @ 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. $\endgroup$
    – J. Doe
    Jan 1, 2020 at 23:54
  • $\begingroup$ You seem to have answered the main question by yourself. Have you thought about posting your own answer $\endgroup$
    – conchild
    Jan 2, 2020 at 11:24
  • $\begingroup$ @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. $\endgroup$
    – J. Doe
    Jan 2, 2020 at 18:10
  • 3
    $\begingroup$ 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). $\endgroup$
    – anon
    Jan 2, 2020 at 20:05

1 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.


  • $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$.
  • $\begingroup$ ($k$ can also be a product of those primes found with factorization, I left this over to shorten the question) $\endgroup$
    – J. Doe
    Jan 3, 2020 at 9:39
  • $\begingroup$ 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. $\endgroup$
    – J. Doe
    Jan 3, 2020 at 9:41
  • $\begingroup$ @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. $\endgroup$
    – fgrieu
    Jan 3, 2020 at 10:05
  • 1
    $\begingroup$ 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. $\endgroup$
    – poncho
    Jan 3, 2020 at 14:40
  • $\begingroup$ @poncho: I'll put that in the answer. My second blatant steal from you today! $\endgroup$
    – fgrieu
    Jan 3, 2020 at 14:50

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.