Do the Möbius function, totient function, sum of divisors and number of divisors uniquely specify a number?

Let $\mu\left(n\right)$ be the Möbius function. Let $\phi\left(n\right)$ be Euler’s totient function. Let $\sigma\left(n\right)$ be the sum of divisors and $\tau\left(n\right)$ be the number of divisors functions. I am curious to know whether or not the system:

$\mu\left(n\right)=a$

$\phi\left(n\right)=b$

$\sigma\left(n\right)=c$

$\tau\left(n\right)=d$

has at most one solution.

Motivation: I remember a number theory assignment I had where we were given particular values for each of these functions and asked to recover the original number. I can’t for the life of me remember how (or if) I managed to solve this problem. I tried to work out a general proof, but couldn’t. I also wrote a loop in maple to check for counterexamples, but haven’t found any yet. I feel like this is something I should know, but probably have forgotten the relevant facts to approaching this problem.

Answer

The answer is No. The smallest counterexamples I could find are {1836, 1824), {5236, 4960}, {5742, 5112}, {6764, 6368}, {9180, 9120} and {9724, 9184}. I think those are all the pairs in which both numbers are less than 10,000.

For example, both $n=1836$ and $n=1824$ satisfy $\mu(n)=0$, $\varphi(n)=576$, $\sigma(n)=5040$ and $\tau(n)=24$.

EDIT: here’s the code of the program I used in GAP.

vec := function(n)
 return [MoebiusMu(n), Phi(n), Sigma(n), Tau(n)];
end;

dic:=NewDictionary([1,2,3,4], true);

for i in [2..10000] do
 v:=vec(i);
 if (LookupDictionary(dic, v) <> fail) then Print(i," <=> ", LookupDictionary(dic, v), "\n"); fi;
 AddDictionary(dic, v, i);
od;

Attribution
Source : Link , Question Author : WWright , Answer Author : Alon Amit

Leave a Comment