A generalization of the Goresky-Klapper conjecture

Abstract

For a fixed integer n ≥ 2, we show that a permutation of the least residues mod p of the form f(x) = Ax[superscript k] mod p cannot map a residue class mod n to just one residue class mod n once p is sufficiently large, other than the maps f(x) = ±x mod p when n is even and f(x) = ±x or ±x [superscript (p+1)/2] mod p when n is odd. We also show that for fixed n the image of each residue class mod n contains every residue class mod n, except for a bounded number of maps for each p, namely those with (k −1, p−1) > (p−1)/1.6n⁴ and A from a readily described set of size less than 1.6n⁴. For n > 2 we give O(n²) examples of f(x) where the image of one of the residue classes mod n does miss at least one residue class mod n.