  Carlitz proved that, for any prime power q other than 2, the group of all
permutations of the finite field F_q is generated by the permutations induced
by degree-one polynomials and x^{q-2}. His proof relies on a remarkable
polynomial which appears to have been found by magic. We show here that no
magic is required: there is a straightforward way to produce a simple
polynomial which has the same remarkable properties as the complicated
polynomial in Carlitz's proof. We also identify the crucial subtlety which
allows such simple polynomials to exist, and discuss some consequences.
