An integer is prime iff $\phi(n) \mid n-1$ and $n+1 \mid \sigma (n)$

I wish to prove

An integer is prime iff $\phi(n) | n-1$ and $n+1|\sigma (n)$ where $\phi$ is Euler's totient function and $\sigma(n)$ is the sum of the positive divisors of n.

I can show from a previous exercise that $\phi(n)|n-1$ implies n is square free.

I also know that $\sigma$ is multiplicative so $\sigma (n)$ is the product of $1+p_i$ for the prime factors of n So $\sigma (n) = n+1+S$ where $S$ is a bunch of extra terms which are divisible by $n+1$ since $n+1|n+1$ and $n+1|\sigma(n)$ so $n+1|\sigma (n)-(n+1)$ or $n+1|S$

I suspect that I need to show $n+1|S$ only if n is prime but am not sure how to do so. Or maybe I'm going in the totally wrong direction?

The other part of the proof is trivial since $\phi(p)=p-1$ and $\sigma (p)=p+1$ for any prime $p$ almost directly from the definitions of these functions.

Solution 1:

Assume $n$ is composite and satisfies the divisibility criteria. From $\phi(n)\mid n-1$ we can gather that $n$ is odd and square-free. Write $n=\prod_{i=1}^{m} p_i$ for distinct odd primes $p_1,\dots, p_m$. We then have that $$\begin{aligned} \sigma(n)=\prod_{i=1}^m (p_i+1) \\ \phi(n)=\prod_{i=1}^m (p_i-1) \end{aligned}$$ Since $\phi(n)\mid n-1$ we can write $n=k\phi(n)+1$ for some $k\in\mathbb{N}$. Since $n$ is composite we have that $k\ge 2$. We then have that $k\phi(n)+2\mid \sigma(n)$. Since $n$ is composite and odd, it has at least two factors and $4\mid \phi(n)$. Thus we have that $k\phi(n)/2+1$ is odd and $k\phi(n)/2+1\mid \sigma(n)/2^{v_2(\sigma(n))}$. It then follows that $$\phi(n)+1\le k\phi(n)/2+1\le \sigma(n)/2^{v_2(\sigma(n))}\le \sigma(n)/2^{m}$$ where the last inequality is since each prime divisor of $n$ contributes at least one factor of two to $\sigma(n)$, so $v_2(\sigma(n))\ge m$. This gives namely that $$1<1+\frac{1}{\phi(n)}\le\frac{\sigma(n)}{2^m\phi(n)}=2^{-m}\prod_{i=1}^{m}\frac{p_i+1}{p_i-1}\le 2^{-m}\cdot \left(\frac{3+1}{3-1}\right)^{m}=1$$ Which violates the strict inequality and we have a contradiction. Thus $n$ cannot be composite and simultaneously satisfy the divisibility criteria.

Note that the question of whether $\phi(n)\mid n-1$ alone is sufficient for concluding $n$ is prime is known as Lehmer's totient problem. Also note that this technique could be used to investigate whether $n$ square-free and $n+1\mid \sigma(n)$ is sufficient for primality. This work can easily be modified to show it is sufficient when $n\not\equiv 3\mod 4$; along with computer testing (if the conjecture is true) one can prove it to be true for all $n\not\equiv -1\mod 2^m$ for any $m$.

Solution 2:

This problem is problem number $\textbf{E2611}$ which appeared in the American Math Monthly. I am reproducing the solution below which is due to Paul Vojta. As in Will Fischer's answer it is very clear that $n=p_{1}p_{2}\ldots p_{k}$ where $p_i$ are odd primes for all $i$. This also implies that $$\phi(n)=\prod_{i=1}^{k}(p_{i}-1)\implies 2^{k}\mid\phi(n)$$ Also note that $$\sigma(n)=\prod_{i=1}^{k}(p_i+1)\implies 2^{k}\mid \sigma(n)$$ Our goal is to show $k=1$. If $k\geq 2$ then $4\mid\phi(n)\mid (n-1) \implies 4\nmid n+1$ and this says that the $v_{2}(n+1)=1 \implies 2^{k-1}\mid\frac{\sigma(n)}{n+1}$. This gives us $$2^{k-1} \leq\frac{\sigma(n)}{n+1}<\frac{\sigma(n)}{n}=\prod_{i=1}^{k}\left(1+\frac{1}{p_i}\right)\leq\left(\frac{4}{3}\right)^{k}$$ which fails to hold for $k\geq 2$.