A solution to the Subbarao relation

Chris Nash

Abstract

1  Definitions

2  Solution of Carlos Rivera's Puzzle 76

We first note the following relations which follow directly from the definitions of f(n) and s(n):

s(n) = å d|n  d (2) n = å d|n  f(d) (3)

By applying the Möbius inversion formula to (3) we have

f(n) = å d|n  m(n/d) ·d (4)

We note both (2) and (4) include a term for d = n that evaluates to n, and so we have the formula

z(n) = (f(n)-n) + (s(n)-n) = d < n å d|n  m(n/d) ·d + d < n å d|n  d = d < n å d|n  (m(n/d)+1) ·d (5)

Since each term in (5) is non-negative we conclude z(n) ³ 0. For equality to hold, either the sum must be empty, or each term must equal zero. An empty sum only occurs in the case n = 1, otherwise we require

m(n/d) = -1  " d|n,  d < n (6)

In particular, this means n cannot have two or more distinct prime factors. If n had distinct prime factors p and q, choose d = n/pq and we have a contradiction with (6). Hence n must be a power of a prime.

Similarly, if n = p^r for some r > 1, choose d = 1 and again we have a contradiction with (6).

Finally it is easy to demonstrate that, if n is prime, f(n) = n-1 and s(n) = n+1.

Hence z(n) = 0 if and only if n = 1, or n is prime.

3  The Subbarao relation

The Subbarao relation

n ·s(n) = 2  mod f(n) (7)

has no composite solutions except for n = 4,6,22.

We have, from (1),

s(n) = 2n+z(n)  mod f(n)

and thus

n ·s(n) = n(2n+z(n))  mod f(n)

Let us assume n is composite and (7) is true. Then

2n2+nz(n)-kf(n) = 2, (8)

for some integer k. The proof now proceeds by cases.

Case I: If n has a repeated prime factor p^r for some r > 1, then p^r-1 divides the left side of (8). Hence p^r-1 must divide 2, so p must be 2, and r must be 2. n = 4 is a known solution. If n = 4m for some odd integer m > 1, some prime factor of m will contribute an additional factor 2 to f(n), so the left-hand side is divisible by 4 while the right-hand side is not, a contradiction.


Case II: Suppose now n = 2p for some odd prime p. We note that z(n) = 2, and considering (8) modulo (p-1) gives


2.22+2.2 = 2  mod (p-1).

Hence (p-1) divides 10, producing the solutions p = 3 and p = 11, corrsponding to the known composite solutions n = 6 and n = 22.


Case III: Suppose now n = 2m for some odd composite number m with no repeated factor. We note that in (5), none of the m terms can be zero, hence every term in the sum is even. Furthermore each prime factor of n contributes at least one factor 2 to f(n). Hence 4 divides every term on the left-hand side of (8), a contradiction, and there are no solutions n of this form.


Case IV: Finally assume n is a product of distinct odd primes. As above, we see z(n) is even, but now show that z(n) is not divisible by 4. Let us define f(x) as the number of prime factors of x. Then (5) becomes


z(n)/2 = d < n å d|n, f(n/d)  is  even  d (9)

We note every term in the sum in (9) is odd. We also note the number of terms in this sum is


2r < = f(n) å r = 1  æ ç è f(n) 2r ö ÷ ø = 2f(n)-1-1,

each choice of 2r factors denoting all combinations of factors of n/d. Since f(n) > 1 in this case, we note the number of terms is therefore odd, hence z(n)/2 is an odd number. As before each prime factor of n contributes a factor of 2 to f(n). Since n is also odd, we have


2n2 = 2  mod 4, nz(n) = 2  mod 4, f(n) = 0  mod 4

and the left-hand side of (8) is again divisible by 4, a contradiction and thus there are no solutions n of this form.

It is immediately verified the Subbarao relation holds for all primes. Summarizing, the only composite numbers satisfying the Subbarao relation are n = 4,6,22.

References

[1]

Richard K. Guy, ``Unsolved Problems In Number Theory'', B37, p.92. (Springer-Verlag, New York, 1994).

[2]

E.Bach; J.Shallit: ``Algorithmic Number Theory''. (Foundation of Computer Science Series, MIT Press, 1996).

[3]

C. Rivera, J. McCranie: ``Puzzle 76. z(n)=sigma(n)+phi(n)-2n'', http://www.sci.net.mx/~crivera/puzzles/puzz_076.htm