A is the set of positive integers and B is A ∪ {0}. Prove that no bijection f: A → B can satisfy f(mn) = f(m) + f(n) + 3 f(m) f(n) for all m, n.
Solution
We must take f(1) = 0, since if f(k) = 0, then f(k2) = 0 also and f is (1, 1). So for any n > 1 we have f(n) ≥ 1. Now suppose n is composite, n = rs with r, s > 1. Then f(n) = f(r) + f(s) + 3 f(r) f(s) ≥ 5. Take p and q so that f(p) = 1 and f(q) = 3. Then we have just shown that p and q are prime. Now take r so that f(r) = 8.
But now f(q2) = f(q) + f(q) + 3 f(q) f(q) = 3 + 3 + 27 = 33, and f(pr) = f(p) + f(r) + 3 f(p)f(r) = 1 + 8 + 3·8 = 33. f is a bijection so we must have q2 = pr, but that is impossible, since p and q are distinct primes.
Comment. How did I come by that? I started playing with small values, but could not reach any obvious contradiction - unfortunately, I did not go as far as 33. So I started to look harder. I noticed a pattern in f(pn). It seemed to be (4n-1)/3. That suggested looking at other f(qn). Sure enough it appeared that if f(q) = 2, then f(qn) = (7n-1)/3. If f(s) = 3, then f(sn) = (10n-1)/3. I then noticed that that implied that f(pnqm) = (4n7m-1)/3. At that point I knew I was almost there because it seemed likely that we could find two different factorisations. So I worked out a few more and found that if f(r) = 8, then f(rn) = (25n-1)/3. Since 251.41=102 I was home, apart from some routine tidying up. At that point I had not proved any of the patterns. In fact, it is easy to show that if f(p) = k, then f(pn) = ( (3k+1)n-1)/3, but it is not necessary for the proof.
© John Scholes
jscholes@kalva.demon.co.uk
11 Apr 2002