2
$\begingroup$

Question: Is there any formula for finding the $\operatorname{gcd}(\phi(n), n)$?

I'm not sure if this is a dumb question, but I couldn't find one myself and not on Wikipedia.

EDIT: To clarify what I'm trying to do:

I'm trying to solve another problem, where I have to plug the greatest common divisor into the Totient function again, and it would be fun if there was an expression for that so it maybe would simplify.

$\endgroup$
8
  • 3
    $\begingroup$ OEIS sequence A009195. $\endgroup$ Mar 15, 2020 at 17:15
  • $\begingroup$ @RobertIsrael Pardon me, I'm quite new to OEIS, the formula section leads to other sequences, does this mean the problem has only been partially solved or? $\endgroup$ Mar 15, 2020 at 17:31
  • 2
    $\begingroup$ Depends on what you really want to do. What is wrong with just $\text{gcd}(\phi(n),n)$? $\endgroup$
    – Somos
    Mar 15, 2020 at 17:43
  • 7
    $\begingroup$ If there were a simpler expression the OEIS would probably have it. This is as simple as it gets unless I am very mistaken. Please edit your question to include your comment in the body of it. $\endgroup$
    – Somos
    Mar 15, 2020 at 17:49
  • 1
    $\begingroup$ @Peter Sorry I was in a hurry yesterday and on phone. Coincidentally, I'm trying to give this problem a try, which you have also worked on. Basically I'm just "doodling" around, trying to simplify the 3rd equation given in the problem and the term $\phi(n\phi(n))$ appeared, and since $n$ and $\phi(n)$ are not necessarily relatively prime, I used the formula $$\phi(nm)=\phi(n)\phi(m)\frac{d}{\phi(d)}$$ where $d$ is $\operatorname{gcd}(m,n)$. $\endgroup$ Mar 16, 2020 at 12:48

1 Answer 1

3
$\begingroup$

There's no known closed expression about what you're asking.

However we can do a little bit better than that if we know the factorization of the integer $ n \ = \ p_1^{k_1}...p_r^{k_r}$

$\phi(n) \ = \ p_1^{k_1}...p_r^{k_r}(\frac{p_1 - 1}{p_1})...(\frac{p_r - 1}{p_r}) \ = \ p_1^{k_1-1}...p_1^{k_r-1}(p_1-1)...(p_r-1)$

$\gcd(\phi(n), n)\ =\ \gcd (p_1^{k_1-1}...p_1^{k_r-1}(p_1-1)...(p_r-1),\ p_1^{k_1}...p_r^{k_r})\ =\\ p_1^{k_1-1}...p_1^{k_r-1}\gcd((p_1-1)...(p_r-1), p_1...p_r)$

$\endgroup$

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .