Bijective Integers.

Sometimes we return to old problems in order to solve them in quicker or nicer ways. I have just done this.

When I was an undergrad I was playing around with powers in residue systems.

Take any $n,m>1$ and consider the numbers $\{0^m, 1^m, 2^m, \mathellipsis, (n-1)^m\}$ in $\mathbb{Z}/n\mathbb{Z}$. I was interested in the values of $m$ that would make this set the biggest that it could possibly be, i.e. $\{0, 1, 2, \mathellipsis, (n-1)\}$. If this happens, let’s say that $(n,m)$ has the bijective property, or that $(n,m)$ is bijective.

Clearly when $n>2$, no even $m$ can give the bijective property for $(n,m)$ (because 1^{2k} = (n-1)^{2k} mod $n$), so I started to look at odd $m$.

I posed myself the following question; “Which $n$‘s are such that $(n,m)$ is bijective for ALL odd $m$?”

Call such an $n$ a bijective integer.

For example if we take $n=5$ then we find that $0^3 = 0$ mod $5, 1^3 = 1$ mod $5, 2^3 = 3$ mod $5, 3^3 = 2$ mod $5, 4^3 = 4$ mod $5$ so that $(5,3)$ is bijective. It is not difficult to check that actually $(5,m)$ is bijective for all odd $m$, so that $5$ is a bijective integer.

Of course, there are others, I found by experimentation that $2,3,5,6,10,15,17,...$ appear to be bijective integers.

I made a big investigation into this, managing to prove that bijective integers are square-free and that $ab$ is a bijective integer if and only if $a,b$ both are. Thus I was able to reduce to studying bijective primes.

I found a very interesting result when studying bijective primes, it appeared that $p$ is a bijective prime if and only if $p$ is 2 or a Fermat prime. This was quite a nice little fact. I managed to prove it by using primitive roots mod $p$, amongst other things.

Back then I was really excited about finding my own results no matter how simple. I have now figured out that my result was actually quite easy to prove.

Returning to this problem I rephrase and provide a nicer proof of this fact.

Clearly $2$ is a bijective prime so we concentrate on odd primes, $p$. The bijective property of $(p,m)$ is simply saying that the “power by $m$” map is an isomorphism of $(\mathbb{Z}/p\mathbb{Z})^{\times}$ with itself, i.e. an automorphism of $(\mathbb{Z}/p\mathbb{Z})^{\times}$.

Now by Fermat’s little theorem the “power by $p-1$” map is the map sending everything to $1$ (since $a^{p-1} = 1$ mod $p$), thus the “power by $m$” map is completely determined by $m$ mod $p-1$. Also since $(a^x)^y = a^{xy}$ we see that composing the “power by $x$” and the “power by $y$” maps gives the “power by $xy$” map.

Putting all this together we find that we get an isomorphism of the group of power maps for powers $1,2,\mathellipsis, p-1$ with $(\mathbb{Z}/p\mathbb{Z})^{\times}$.

So $(p,m)$ is bijective if and only if $m$ is coprime to $p-1$ (because by the above isomorphism, the $m$th power map has an inverse if and only if $m$ has an inverse mod $p-1$).

This tells us that $p$ is a bijective prime if and only if $p-1$ is coprime to ALL odd integers, i.e. that $p-1 = 2^k$ for some $k$, hence that $p = 2^k + 1$ is a Fermat prime!

We conclude that $n$ is a bijective integer if and only if it is a product of distinct numbers from the set of Fermat primes and $2$ (Fermat primes are coprime to each other so we always get square-free numbers when we multiply distinct ones).

Since there are only $5$ Fermat primes known, this means that there are not many known bijective integers (there are $2^6 = 64$ known ones).