Let $p$ be prime and $n\geq 1$. Let $g$ be the integer equivalent of some generator for $(\mathbb{Z}/p\mathbb{Z})^ \times$.

Let $k\in \{0,1,2,...\} \subseteq \mathbb{Z}$ such that $p-1$ does NOT divide $k$.

I want to show that $g^{0p^nk}+g^{p^nk}+g^{2p^nk}+...+g^{(p-2)p^nk} \equiv 0$ (mod $p^n)$

I tried writing the sum as $g^{0p^nk}+g^{p^nk}+g^{2p^nk}+...+g^{(p-2)p^nk}=\frac {g^{(p-1)p^nk}-1}{g^{p^nk}-1}$ but I don't see why this would have to be divisible by $p^n$

  • 1
    $\begingroup$ What's $n$? Taking $p=3=k$ we get $0^3+1^3+2^3=9$ so, yes, it is divisible by $3^2$, but not by $3^3$. $\endgroup$ – lulu Nov 9 '18 at 0:18
  • $\begingroup$ @lulu You're right, I must have made a mistake. I hope I fixed the question now. $\endgroup$ – Pascal's Wager Nov 9 '18 at 0:36
  • $\begingroup$ Looks like it is about the multiplicative order of $g^{p^n k}$ in $(\mathbb{Z}/p^n\mathbb{Z})^ \times$ being a non-trivial divisor of $p-1$ $\endgroup$ – random Nov 9 '18 at 14:08

You are almost done with the formula for the geometric sum as fraction which you write. Just remember that:

  1. The multiplicative group $(\Bbb Z/p)^\times$ ist cyclic of order $p-1$. So $g^{(p-1)k} \equiv 1$ mod $p$.

  2. On the other hand, the condition that $k$ does not divide $p-1$ implies that $g^{p^n k} \equiv g^k \not \equiv 1$ mod $p$, in other words, the denominator of your fraction is not divisible by $p$.

  3. As you just asked in $a \equiv b$ (mod $p$) implies $a^{p^n} \equiv b^{p^n}$ (mod $p^n$)?, the congruence from 1. further implies that $g^{(p-1)k p^n} \equiv 1^{p^n} = 1$ mod $p^n$. In other words, the numerator of your fraction is ...


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.