6
$\begingroup$

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?

  • 1
    See my answer here: http://math.stackexchange.com/questions/25849/other-ways-to-deduce-cyclicity-of-the-units-of-certain-groups/26$0$19#26$0$19 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.2011-04-08

1 Answers 1

4

First we claim that for any $k\geq 0$ we can write $g^{p^{k-1}(p-1)}=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)}=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 :).

  • 0
    Don't you mean $g^{p^{k - 1}(p - 1)}$, and similarly with some of the other expressions?2011-04-10