Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

I saw this theorem referenced in a paper on performing shuffles in an array. There is a proof on pages 20-21 of the this link, but the proof is very terse and omits a lot of intuition.

Is there an intuitive explanation for why this theorem is true, or at least a proof that omits fewer details?

share|cite|improve this question
When I follow that link, I see the message "pages 3-98 are not shown in this preview". – Matthew Conroy Apr 8 '11 at 4:55
Wow, I don't know why it gave me so much more of a preview. – jonderry Apr 8 '11 at 7:16
See my answer here:… It is a little more intuitive, but also more advanced than you might want. I doubt there is an extremely intuitive reason that is also accesible when you are first learning this stuff. – Barry Smith Apr 8 '11 at 10:50
up vote 4 down vote accepted

First we claim that for any $k\geq 0$ we can write $$g^{p^{k-1}p}=1+a_kp^k\qquad\text{where }p\nmid a_k$$ Clearly $g^{p-1}\equiv 1\pmod{p}$ and hence $g^{p-1}=1+a_0p$ for some $a_0$. Note that $p\nmid a_0$ because otherwise $g^{p-1}\equiv 1\pmod{p^2}$ (contradiction to the fact that $g$ is a primitive root mod $p^2$). Assume that $g^{p^{s-1}p}=1+a_sp^s$ where $p\nmid a_s$. It follows $$g^{p^s(p-1)}=1+a_sp^{s+1}+ \text{ multiple of }p^{s+2}=1+a_{s+1}p^{s+1}$$ If $p\mid a_{s+1}$ then $p^{s+2}\mid a_sp^{s+1}$ which implies that $p\mid a_s$ (contradiction!). Thus $p\nmid a_{s+1}$.

Now we claim that for $k\geq 2$, the order of $g$ mod $p^k$ is $p^{k-1}(p-1)$. For $k=2$, the statement is true. Assume the order of $g$ mod $p^s$ is $p^{s-1}(p-1)$. Since $$g^{p^s(p-1)}=1+a_{s+1}p^{s+1}$$ clearly $g^{p^s(p-1)}\equiv 1\pmod {p^{s+1}}$. Suppose $l$ be a number such that $g^l\equiv 1\pmod {p^{s+1}}$. Then obviously $g^l\equiv 1\pmod{p^s}$. Since $p^{s-1}(p-1)$ is the order of $g$ mod $p^s$, then $l=tp^{s-1}(p-1)$. Now $$g^l=g^{tp^{s-1}(p-1)}=1+ta_sp^s+\text{ multiple of }p^{s+1}$$ Since $g^l\equiv 1\pmod {p^{s+1}}$ then $p^{s+1}\mid ta_sp^{s}$. But $p\nmid a_s$. Hence $p\mid t$. Write $t=pt_2$. It follows that $l=t_2p^s(p-1)$ and we conclude that $p^s(p-1)$ is the order of $g$ mod $p^{s+1}$.

The case that $g$ is primitive root mod $p$ is left to the reader :).

share|cite|improve this answer
Don't you mean $g^{p^{k - 1}(p - 1)}$, and similarly with some of the other expressions? – jonderry Apr 10 '11 at 18:28

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

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