# What's the greatest common divisor of $\phi(n)$ and $n$, where $\phi(n)$ is the Euler Totient Function?

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.

• OEIS sequence A009195. – Robert Israel Mar 15 '20 at 17:15
• @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? – Casimir Rönnlöf Mar 15 '20 at 17:31
• Depends on what you really want to do. What is wrong with just $\text{gcd}(\phi(n),n)$? – Somos Mar 15 '20 at 17:43
• 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. – Somos Mar 15 '20 at 17:49
• @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)$. – Casimir Rönnlöf Mar 16 '20 at 12:48

## 1 Answer

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