# 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.

• I think something might be going wrong with your analysis on $\sigma(n)$. If you take $n = pq$, then $\sigma(n)$ should be $1 + p + q + pq = n +1 + p + q$, but those extra terms are certainly not divisible by $n+1$... Nov 14, 2015 at 16:02
• How do I prove that those extra terms are not divisible by n+1? That would prove the theorem if I could do that since it would imply that n+1 dividing sigma n implies n is prime since if n is composite, it reaches this contradiction Nov 14, 2015 at 16:24
• @topoquestion It's possible that squarefree plus $n+1 \mid \sigma(n)$ is enough to imply $n$ is prime, but this doesn't seem to be for any obvious local reasons. There are some integers satisfying $n+1 \mid \sigma(n)$ and many of them are divisible by $2^2$, but $n=650$ is not! This suggests it might be necessary to glean more information from $\phi(n) \mid n-1$ than just "$n$ is squarefree": in fact, there isn't a single known composite $n$ satisfying $\phi(n) \mid n-1$ (this is a conjecture of Lehmer), so this is a rather strong assumption. Nov 14, 2015 at 16:59
• 650 is not square free but is divisible by $5^5$ Nov 14, 2015 at 20:20
• This is an exercise from an old edition of Burton's elementary number theory that appears gone in later editions so perhaps it is not provable as easily as most exercises in the text if at all. Nov 14, 2015 at 20:26

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$.
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$$.