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$ – Robert Israel Mar 15 '20 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$ – Casimir Rönnlöf Mar 15 '20 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 '20 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 '20 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$ – Casimir Rönnlöf Mar 16 '20 at 12:48
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$

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.