A curious inversion problem

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.


Comments 6

  1. Michael Knapp

    Am I misunderstanding the problem? For n=2, I find two solutions, f(x)=x and f(x)=x+1. That’s fewer than n+2. Also, for n=16, I find 28 (divisible by 7) solutions. These are f(x)=ax+b with:
    a=1, b=0, 8
    a=7, b=0, 2, 4, 6, 8, 10, 12, 14
    a=9, b=0, 8
    a=15, b=0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15.

    Am I missing solutions?

    1. Post

      I think you’ve understood it perfectly. We excluded n=2 as a special case, since 1=-1.

      For n=16, we may have miscounted! I appreciate the catch. Your count looks right to me. I’ll double check it tomorrow with my student.

    1. Post

      Thanks! I’ll take a look as soon as I’m not worried about the spoiler anymore 🙂

      I spent a little more time with the problem today with my student, and I’ve got some more insight into what the appropriate conjectures should be:

      Let A(n) be the number of functions of the form ax+b that are their own inverse in mod n.

      Conjecture 1. If a and b are relatively prime, then A(ab) = A(a)A(b).

      Conjecture 2. For p an odd prime, A(p^m) = p^m+1.

      If I get a chance to spend a few more minutes, I should be able to write out the rules for powers of 2. I’m pretty sure A(2^m) = 2^m + 2 + 2^(m-1) + 2 = 4(2^(m-2)+2^(m-3)+1). I need to check that one again to make sure I’ve got all the details right.

      In any case, if my conjectures are right–and they look much, much better to me than my old, discredited one, then it shouldn’t be hard to write out a general formula.

  2. Michael Knapp

    Dan, I think you’re right except that your formula for A(2^m) only works for m>2. I get something different for A(2) and A(4).

    1. Post

      Thanks again. I meant to mention that A(2) = 2 and A(4) = 6 (do I have that right? I’m not looking at my notes).

Leave a Reply

Your email address will not be published. Required fields are marked *