Prove that an integer $n \ge 2$ is a prime if and only if $\phi (n)$ divides $(n - 1)$ and $(n + 1)$ divides $\sigma (n)$. [Here $\phi$ is the Totient function and $\sigma $ is the divisor - sum function.]
HIDE: Hint $n$ is squarefreeProblem
Source: Indian Postal Coaching 2008 set 4 p2
Tags: number theory, primes, prime, prime numbers, divides
27.05.2020 09:21
I think the problem should be $n>2$ because $n=2$ doesn't work
27.05.2020 14:38
Note that since $gcd(n,n-1)=1$ we have $(n-1)^{n-1}\equiv 1\pmod{n}$ and hence we have $ n$ is odd.As shown before $n$ is square free. Since $\phi(n)| n-1 $ we can write $n=k\phi(n)+1$ for some $k$. Assume $n$ is composite so $ k\ge 2$. We then have that $k\phi(n)+2|\sigma(n)$. Since $ n$ is composite and odd, it has at least two factors and$4|\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. Hence the only numbers that satisfy the condition are the prime numbers.