How many integers satisfy $(n-3)(n+1)=\phi(n)\cdot \sigma(n)$?

87 Views Asked by At

Note that $\sigma(n)$ is the sum, not the number, of divisors. I have found the solutions $n=15, 35, 143$ using a rudimentary search. Perhaps proving that $n$ is semiprime would be significant progress, but we don't know that for sure.

2

There are 2 best solutions below

1
On

Too long for a comment:

If you consider a semiprime $n=pq$, then your equation is simply $$(pq-3)(pq+1)=(p-1)(q-1)(1+p+q+pq)$$ which (after algebraic manipulations) is equivalent to $$p^2+q^2-2pq-4=0$$ or simply $$(p-q)^2=2^2$$ Thus $p,q$ must be twin primes. Indeed

for $(p,q)=(3,5)$ you get $n=15$

for $(p,q)=(5,7)$ you get $n=35$

for $(p,q)=(11,13)$ you get $n=143$

and so on.

0
On

So we know a few things:

  1. No solution when $n$ is prime (your comment);
  2. $n = a^2 - 1$ when $n$ us a semiprime (Crostul's solution);
  3. If $p^2 \ | \ n$ then $p = 3$ and $3^3 \!\not| \ n$ (lulu's comment).

Here is a sketch to deal with the rest. Very likely that there are no new solutions, but I have not work it out yet.

The upshot is that we should be able to prove that $RHS > LHS$ when $n$ is not in the cases above and large enough. Let's do this.

It is easy to show that if $n = \prod p_i^{e_i}$ as a prime factorization, then $$ \frac{\phi(n)\sigma(n)}{n^2} = \prod\left(1 - \frac{1}{p_i^{e_i+1}}\right). $$

Also it is easy to see that $n>3$ and $(n-3)(n+1) > n(n-3)$. It suffices to show that when $n$ is not in the known case and large enough, $$ 1 - \frac3n \geq \min\left\{1 - \frac{1}{p_i^{e_i+1}}\right\} > \prod\left(1 - \frac{1}{p_i^{e_i+1}}\right), $$ or equivalently, $$ \frac3n \leq \max \left\{\frac{1}{p_i^{e_i+1}}\right\}, $$ or it is sufficient to prove that, $$ n \geq 3\min\{3^3, p_i^2\}, $$ where $p_i$ ranges through the prime factors of $n$.

The only $n$ which is a product of two primes and not excluded yet is $n = 3^2$, for which you can easily test and exclude it. Now we only need to consider the case when $n$ is at least a product of three primes (possibly $9|n$). If you can test by hand the cases $n \leq 81$ (which should be a fairly quick, and this is where I have not spent time on it yet), then it suffices to show that $n \geq 3p^2$, where $p$ is the smallest prime divisor of $n$. But this is quite obviously true.