On permutations derived from integer powers $x^n$

Abstract

We present a general theorem characterizing the relationship between the prime base $p$ representations of non-negative integers $x$ and their positive integer powers, $x^n$. For any positive integer $l$, the theorem establishes the existence of bijective mappings (permutations) between all $p^l$ members $x$ of each non-zero residue class mod $p$ satisfying $x<p^{l+1}$. These mappings are obtained as the integer part of $x^p{p}^{-\alpha }$ for a particular positive integer $\alpha$, depending on $n$ and $p$, called the "coding shift", for which an explicit formula is given. For relatively prime $n$ and $p$, $\alpha =1$ and the result follows directly from properties of the multiplicative group of invertible elements modulo $p^{l+1}$. We extend our result for general $n$ also to identify the coding shift required to obtain such bijective mappings for members of the zero residue class mod $p$, demonstrating that such bijective mappings (or encodings) can be found for any finite $l$ and for all positive integers $x<p^{l+1}$.

16 Pages, 2 figures