3
$\begingroup$

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?

$\endgroup$
  • 1
    $\begingroup$ Prove sum of primitive roots congruent to μ(p−1)(modp) $\endgroup$ – kelalaka Jan 1 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 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 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 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$ – runway44 Jan 2 at 20:05
1
$\begingroup$

(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$.
$\endgroup$
  • $\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 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 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 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 at 14:40
  • $\begingroup$ @poncho: I'll put that in the answer. My second blatant steal from you today! $\endgroup$ – fgrieu Jan 3 at 14:50

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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