46
$\begingroup$

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.

  • 1
    The value of $n \phi(n)$ uniquely determines $n$, so one function is all you need.2010-11-22

2 Answers 2

29

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; 
  • 0
    Thanks for sharing the code! I might try modifying this myself to see what number theoretic properties the multiple solutions have in common.2010-11-22
16

First, congratulations on asking a number theory question which is quite unlike any I have seen before. It's certainly more fun to read about questions like this rather than computing $a^b$ modulo $n$.

Regarding the assignment you got: one can certainly find particular values of $a$, $b$, $c$ and $d$ such that there is exactly one $n$ solving the equations. For instance, if $p$ is a prime number then taking $a = -1$, $b = p-1$, $c = p+1$, $d = 2$ has the unique solution $n = p$: $\tau(n) = 2$ forces $n$ to be prime and thus $\varphi(n) = n-1$.

Although I am a number theorist, I don't have an expert opinion on the general question. (I'm not really "the right kind" of number theorist to answer this question. You might ask Carl Pomerance, for instance.) I suppose the more reasonable guess is that there are values of $a,b,c,d$ which yield more than one solution.

Probably the first thing to do is what you're doing: search for counterexamples by computer. When you get tired of doing that, let us know how far you looked (and, of course, whether you've found any). The second thing to do is to come up with a heuristic on how often one might expect multiple solutions to be found...

  • 0
    @WWright As you're ok with that, and I'm certainly curious about the answer too (although sadly I've no time to work on it at the moment), I've just posted the follow up question.2010-11-22