A curious inversion problem

May 13, 2013

I’ve been exploring a new problem with a couple of students recently that I find incredibly compelling, and I thought I’d mention it here. The main idea is looking at the behavior of functions of the form f(x) = ax + b in various mods. There’s actually a huge amount to explore here, from fixed points to invertibility to the length of loops when you repeatedly apply functions. But one apparent pattern in particular blew me away.

The question is this: in mod n, how many functions f(x)= ax +b are their own inverses?

For example, the function f(x) = 5x + 2, applied twice in mod 12, is equal to the identity. It’s direct to check: f(f(x)) = f(5x+2) = 5(5x+2) + 2 = 25 x + 10 + 2 = x (mod 12).

We proved that there are at least n+1 self-invertible functions of this form for odd n, and n+2 for even n… these are our minimal cases. But what about the non-minimal cases?

We worked out the cases up to 28 by hand, and bewilderingly, for every non-minimal n, the number of self-invertible functions was always a number that completely factored as products of 2s and 3s. For example, in mod 12 there are 24 = 2x2x2x3 linear functions that are their own inverses.

I can see no reason why this should be true, or what these things even have to do with each other. My hunch is that it may just be a coincidence. Still, if it is a coincidence, it’s a pretty marvelous one, working for n = 8, 12, 15, 16, 20, 21, 24, 28, which, by our reckoning, are the non-minimal cases. How long should we expect such a pattern to hold before we suspect that something is going on?

In any case, the behavior of these functions mod n has totally captured me for the time being. I can’t believe I’ve never thought about them with students before.

Subscribe
Notify of
guest
0 Comments
Inline Feedbacks
View all comments