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

About these ads

This entry was posted on January 9, 2012 at 11:43 am and is filed under Elementary Number Theory, Number Theory. You can follow any responses to this entry through the RSS 2.0 feed. You can leave a response, or trackback from your own site.

Dedekind's Paradise

Bijective Integers.

Like this:

Leave a Reply Cancel reply

Follow “Dedekind's Paradise”