I recently posted this interesting inversion problem:

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

I offered a conjecture that, a bit later, is almost hilariously false. (Don’t feel bad if you do this: I always try to get my hilariously misperceptions stated, disproved, and out of the way as soon as possible, and nobody gets hurt in the process.)  But I’d like to put forward a few better ones now that I’ve thought about the problem a bit more.

Conjecture 1. Let A(n) be the number of functions ax+b that are their own inverses mod n. If n and m have no prime factors in common, then A(nm) = A(n)A(m).

Example. If I want to know A(35), the number of functions ax + b that are their own inverses mod 35, then I simply need to find the product of A(5) and A(7).

Two quick things to mention. First, if Conjecture 1 is true, then A is an example of a homomorphism, which means that it preserves certain structural elements between where it’s coming from (the domain) and where it’s going (the range). These maps that preserve structure are the lifeblood of mathematics, because they allow you to take what you know about one area and apply it to another; they also allow you to build up to complete solutions from simpler cases. In this case, we just need to know how A acts on primes and powers of primes. After that, Conjecture 1 allows us to multiply them together to get any number, and still keep track of what will happen, as in the example.

It turns out that there are two different cases we need to treat: odd primes (3, 5, 7, 11…) and even primes (2).

Conjecture 2. If p is an odd prime, then A(p^n) = p^n + 1.

Conjecture 3. For positive integer m>2, A(2^m) =  2^m + 2 + 2^(m-1) + 2 = 4(2^(m-2)+2^(m-3)+1). For m=1 or 2, we have A(2) = 2 and A(4) = 6.

Now I got these conjectures by writing out the values of A(n) up to n = 40 in a chart with a student and playing around with them. If you’re reading this without having done that, or having background with problems like this, then it may seem mysterious how I came up with these conjectures, particularly conjecture 3. But it’s really just a matter of spending the time on it, and writing down the algebra to reflect the patterns you’re seeing.

To prove these conjectures, on the other hand, takes a little more subtlety, and more algebra too. First, you have to look at how ax+b behaves when applied twice: it’s a(ax+b)+b = (a^2)x + ab + b = (a^2)x + (a+1)b. For this to equal x in mod n, we must have a^2 = 1 and (a+1)b = 0 mod n. This alone makes the count a lot easier: just look for numbers that square to 1 mod n.

I’m not going to get into full proofs, but I will share Paul Lockhart’s elegant dispatching of the problem. Paul Salomon passed the problem to Paul Lockhart, and seeing the latter Paul’s elegant thinking is a pleasure. However, he pulls out mathematics and shorthand that might be intimidating if you’re not familiar with it. If you are, then you can add some details and prove all three conjectures with not too much more effort.

Here’s the question I’ve been kicking around since: the first example I happened to calculate was A(12), which equals 24. This reminded me of so-called perfect numbers, which have the property that the sum of their factors is precisely twice the number itself, i.e., 1,2,3, and 6 are the factors of 6, and 1+2+3+6 = 12, which is twice 6. Usually perfect numbers are described in terms their proper factors—ignore the 6, and they sum to themselves. However, it’s just as easy to describe them this way, and that makes my thought easier to follow.

Question. How many n have the property that A(n)=2n? Is n=12 the only option, or are there infinitely many? Or perhaps there’s a finite list of number that work?

I haven’t thought about this one at all yet, but it seems like an interesting place to go. If anyone has any breakthroughs, let me know!