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 and consider the numbers in . I was interested in the values of that would make this set the biggest that it could possibly be, i.e. . If this happens, let’s say that has the **bijective property, **or that is **bijective**.

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

I posed myself the following question; “Which ‘s are such that is bijective for ALL odd ?”

Call such an a **bijective integer.**

For example if we take then we find that mod mod mod mod mod so that is bijective. It is not difficult to check that actually is bijective for all odd , so that is a bijective integer.

Of course, there are others, I found by experimentation that appear to be bijective integers.

I made a big investigation into this, managing to prove that bijective integers are square-free and that is a bijective integer if and only if 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 is a bijective prime if and only if is 2 or a **Fermat prime.** This was quite a nice little fact. I managed to prove it by using primitive roots mod , 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 is a bijective prime so we concentrate on odd primes, . The bijective property of is simply saying that the “power by ” map is an isomorphism of with itself, i.e. an automorphism of .

Now by Fermat’s little theorem the “power by ” map is the map sending everything to (since mod ), thus the “power by ” map is completely determined by mod . Also since we see that composing the “power by ” and the “power by ” maps gives the “power by ” map.

Putting all this together we find that we get an isomorphism of the group of power maps for powers with .

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

This tells us that is a bijective prime if and only if is coprime to ALL odd integers, i.e. that for some , hence that is a Fermat prime!

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

Since there are only Fermat primes known, this means that there are not many known bijective integers (there are known ones).

## Leave a Reply