Let $\phi$ Euler totient function and $\sigma$ is power of sum divisor function, I want to know if there is any standard basics in number theory show us :When is $\gcd(\sigma(n),\phi(n))$ is a prime number ? with $n$ is a postive integer

  • $\begingroup$ Maybe it i helpful if you indicate what you are looking for: a way of finding some of these numbers with a computer, or a general categorization. $\endgroup$ – Reiner Martin Jun 29 '17 at 19:55
  • $\begingroup$ By "power of sum divisor function", do you mean $\sigma_x(n)=\sum_{d\mid n} d^x$ ? $\endgroup$ – user228113 Jun 29 '17 at 20:01
  • $\begingroup$ yes , this what i meant !!!!!! $\endgroup$ – zeraoulia rafik Jun 29 '17 at 20:06

As helpful fact note that both functions $\phi$ and $\sigma$ are multiplicative. This implies that if the prime decomposition of $n$ is $p_1^{a_1}\cdot\ldots\cdot p_k^{a_k},$ then $$ \phi(n) = \phi(p_1^{a_1})\cdot\dots\cdot \phi(p_k^{a_k}), $$ and similarly for $\sigma.$ Next, note $\phi(p^a) = p^{a-1}(p-1)$ and $\sigma(p^a)=1+p+\cdots+p^a.$ This makes it easier to decide whether $\gcd(\sigma(n),\phi(n))$ is prime.

For example, if $p$ is any odd prime, then $$ \gcd(\sigma(p),\phi(p)) = \gcd(p-1,1+p) = 2, $$ which is prime. But there are other numbers, such as $6=2\cdot 3,$ or $10=2\cdot 5,$ or $468=2^2\cdot 3^2\cdot 13.$


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.