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 mth 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).

 

Advertisements

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s


%d bloggers like this: