If $n$ is square-free and $n+1 \mid \sigma(n)$, is $n$ a prime?

990 Views Asked by At

As the title says, is $n$ being square-free together with $n+1 \mid \sigma(n)$ sufficient to show $n$ is prime?

It is well-known that if $\varphi(n)\mid n-1$ and $n+1 \mid \sigma(n)$, then $n$ is a prime (see e.g. An integer is prime iff $\phi(n) \mid n-1$ and $n+1 \mid \sigma (n)$). Also it is a well-known open problem - Lehmer's totient problem - whether $\varphi(n)\mid n-1$ itself implies that $n$ is a prime. Since $\varphi(n)\mid n-1$ implies that $n$ is square-free, this makes me wondering what is known about the problem in between these two, i.e. $n$ being square-free together with $n+1 \mid \sigma(n)$.

I've checked by brute force that the conjecture holds up for $n$ being a product of any of the first $31$ primes. As for the proof, we can rule out product of two primes easily as $n=pq$ and $pq+1\mid \sigma(n)=(p+1)(q+1)=pq+p+q+1$ implies $pq+1\mid p+q$ and then we show $pq+1>p+q$ contradicts this result. But it does not seem to generalize to more primes that simply. It might be also that this problem is open, in that case I have yet to find a reference.

Update: I've found a proof that only even $n$ that satisfies the conditions is $n=2$, pushing the possible counterexample to odd numbers only.

To see this let $n=2\prod_{i=1}^{k} p_i$ where $p_i=2^{e_i}d_i-1$ with $e_i \geq 1$ and $d_i$ odd. Now we have two possibilities, either $e_i=1$, or $e_i \geq 2$. If $e_i=1$, then $d_i \geq 3$, and we have

$$ 2^{e_i}d_i-1 \geq 2d_i-1\geq \sqrt[k]{\frac{3}{2}} d_i $$ where the last inequality follows from $(2-\sqrt[k]{\frac{3}{2}})d_i\geq (2-\sqrt[k]{\frac{3}{2}})3\geq 1$, which holds for $k \geq 1$.

If on the other hand $e_i\geq 2$, then

$$ 2^{e_i}d_i-1 \geq 4d_i-1\geq \sqrt[k]{\frac{3}{2}} d_i $$ this time because $(4-\sqrt[k]{\frac{3}{2}})d_i\geq (4-\sqrt[k]{\frac{3}{2}})\cdot 1\geq 1$, which again holds for $k \geq 1$.

Either way we get $2^{e_i}d_i-1\geq \sqrt[k]{\frac{3}{2}} d_i$. But then $$ n+1=2\prod_{i=1}^{k}(2^{e_i}d_i-1)+1\geq 2 \prod_{i=1}^k \sqrt[k]{\frac{3}{2}} d_i +1=3\prod_{i=1}^{k}d_i+1 $$ and at the same time $$ n+1\mid\sigma(n)=(2+1)\prod_{i=1}^{k} 2^{e_i}d_i=3\cdot 2^{\sum e_i}\prod_{i=1}^k d_i. $$ Since $n+1$ is odd, we have $n+1 \mid 3\prod_{i=1}^k d_i$ and so $n+1 \leq 3\prod_{i=1}^k d_i$. But these results are contradictory as we have $$ 3\prod_{i=1}^{k}d_i+1\leq n+1 \leq 3\prod_{i=1}^k d_i. $$

Update 2: Furthermore any counterexample must have $n \equiv 3 \pmod 4$. This follows from C.S.'s argument in the linked answer: If $4\mid n-1$, then $2\mid n+1$ and $4\nmid n+1$. So $v_2(n+1)=1$. If $n$ has $k$ odd prime factors then $2^k \mid \sigma(n)$. But then $2^{k-1}\mid \frac{\sigma(n)}{n+1}$ and in turn $$ 2^{k-1}\leq \frac{\sigma(n)}{n+1}<\frac{\sigma(n)}{n}=\prod_{p\mid n} \frac{p+1}{p}\leq \prod (1+\frac{1}{3})=\Big(\frac{4}{3}\Big)^k $$ which does not hold for $k \geq 2$, so $k=1$ and $n$ is a prime.

1

There are 1 best solutions below

6
On

Here's a proof that $n$ can't have just three odd prime factors, say $n=pqr$ where $p<q<r$.

We have \begin{eqnarray*} &&pqr+1|pqr+pq+pr+qr+p+q+r+1 \\&\implies & pqr+1|pq+pr+qr+p+q+r \end{eqnarray*}

We can make use of the following: $r-1>q>p+1$ and obtain $qr>(p+1)r$, $qr>(p+1)(q+1)$.

Adding these up gives \begin{eqnarray*} pqr\geq3qr&>&qr+(p+1)r+(p+1)(q+1)\\ &=&pq+pr+qr+p+q+r+1 \end{eqnarray*}


We can make this observation.

If $n=\prod_{i=1}^{k}p_i$, i.e. it has $k$ prime factors and if $p_i\geq \frac{1}{2^{1/k}-1}$ for each $1\leq i\leq k$, then we have $$1<\frac{\sigma(n)}{n+1}<\frac{\sigma(n)}{n}<2$$

In a similar vein, if $n=pqrs$ has 4 odd prime factors, then $$1<\frac{\sigma(n)}{n+1}=\frac{(p+1)(q+1)(r+1)(s+1)}{pqrs+1} \leq \frac{4\times6\times8\times12}{3\times 5\times 7\times 11 +1}<2$$