15
$\begingroup$

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.

$\endgroup$
  • 1
    $\begingroup$ 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$... $\endgroup$ – Eric Auld Nov 14 '15 at 16:02
  • $\begingroup$ 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 $\endgroup$ – topoquestion Nov 14 '15 at 16:24
  • 1
    $\begingroup$ @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. $\endgroup$ – Erick Wong Nov 14 '15 at 16:59
  • 1
    $\begingroup$ 650 is not square free but is divisible by $5^5$ $\endgroup$ – topoquestion Nov 14 '15 at 20:20
  • 1
    $\begingroup$ 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. $\endgroup$ – topoquestion Nov 14 '15 at 20:26
7
+50
$\begingroup$

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

$\endgroup$
  • $\begingroup$ Nice answer Will! I will wait for a couple more days in search of a maybe better answer. If nothing better comes I will award the bounty to you. $\endgroup$ – Stefan4024 Dec 7 '17 at 5:18
  • $\begingroup$ Thanks! In the meantime, this proof can probably be refined and modified or inspire better ones since we at least now have an idea of how to approach it. $\endgroup$ – Will Fisher Dec 7 '17 at 5:40

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.