The order of the number of integer pairs satisfying certain arithmetical function relationships
Solution 1:
As all of $\mu$, $\tau$, $\phi$, and $\sigma$ are multiplicative, if $(a,b)$ is such a pair and $n$ is relatively prime to $ab$ then $(an,bn)$ is another pair. So, as there is at least one pair there are an infinite number of them, and for $N$ large enough there is a constant C such that there are at least $CN$ such pairs. Also, if $(c,d)$ is another such pair with $(c,d)$ with $cd$ relatively prime to $ab$ then $(ac,bd)$ and $(ad,bc)$ are more pairs.
If we define a primitive pair as a pair that cannot be decomposed as above, then I suspect that there are an infinite number of primitive pairs, but I have no idea how to prove it.
Edit: In the answer to this question the pairs {1836, 1824), {5236, 4960}, {5742, 5112}, {6764, 6368}, {9180, 9120} and {9724, 9184} are found so there is at least one such pair.
Added
To motivate the intuition that there are probably an infinite number of primitive pairs, here is a simple algorithm for computing relative prime pairs:
- Choose a set of small primes $B$ (for example the primes less than 20)
- Compute a set of primes $P$ such that for $p\in P$ both $\sigma(p)=p+1$ and $\phi(p)=p-1$ factor completely using the primes in $B$
- For each prime in $P$ create a variable $X_p$, where $X_p=1$ if $p|m$, $X_p=-1$ if $p|n$ and $X_p=0$ otherwise.
- Each member of $B$ creates 2 linear equality constraints on the $X_p$ and we add another constraint $\sum_{p\in P}X_p = 0$ constraining $m$ and $n$ to have the same number of prime factors. Since they are square free and have the same number of prime factors, both $\mu$ and $tau$ will be equal.
- Enumerate the $\{-1,0,1\}^k$ lattice points that satisfy the constraints. These will give the prime factors of $m$ and $n$.
In theory step 5 can be problematic, in practice it is easy to find many. For example, letting $B$ be the primes less than 20, letting $P$ be the qualifying primes less than 1000, we quickly get hundreds of pairs, the smaller of which are: (15265, 15169), (27962, 26355), (30199, 30217), (64255, 63791), (66526, 62535) (72713, 72703), (89089, 89585), (149739, 145915), (166315, 165319), (182942, 171795), (233597, 235135), (307021, 307951), (344137, 344129), (392227, 391859), (483769, 485317), (622599, 605815), (873301, 876211), (967759, 968297),
It is left as an exercise to the reader to extend this to non square free pairs.
As the size of $P$ seems to grow much faster than $B$ it is plausible that we will generate more new pairs as we grow $B$.