Given a prime $p$, the function $f_k=x^k \mod p$ will sometimes be a permutation of congruence classes of $\{0, 1, \ldots p-1\}$ mod $p$. These are $k$ which are relatively prime to $p-1$. Call these $f_k$ the power permutations.
Similarly, $g_k(x)=x + k \mod p$ is a permutation. Call these the shift permutations;.
I have seen experimentally that when $p \neq 3 \mod 4$, the power permutations and the shift permutations generate $S_p$ the symmetric group on $p$ elements. Is there an easy way to prove this?
I know if I can combine these operations to get an arbitrary polynomial, then I know I can get an arbitrary permutations (by interpolation). I also know if I can get a single consecutive transposition, I can combine it with the shift permutation to get every permutation. But I have been unable to do either.