Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

A few weeks ago I discovered and proved a simple identity for Euler's totient function. I figured that someone would have already discovered it, but I haven't been able to find it anywhere.

So I was hoping someone would be able to tell me whether or not they've seen this identity.

Here it is:

$$\phi(n)=\phi(\operatorname{rad}(n))\left(\frac{n}{\operatorname{rad}(n)}\right)$$

where $\operatorname{rad}(n)$ is the radical or square-free kernel of $n$, i.e. the product of the distinct prime factors of $n$.

I have omitted the proof because firstly, I'm still learning MathJax and am afraid it will take quite a long time to type out. And secondly, I believe it is intuitive enough that most people familiar with the totient function should be able to see that it's true.

Like I said, it is a pretty simple identity, but nevertheless; it seems like it could be fairly useful. It would be a bit easier to calculate $\phi(n)$ for large-ish $n$ with this identity, without the help of a program or totient function calculator.

Ex: $$\phi(450)=\phi(2\cdot3^2\cdot5^2)=\phi(2\cdot3\cdot5)\left(\frac{2\cdot3^2\cdot5^2}{2\cdot3\cdot5}\right)=(1\cdot2\cdot4)(3\cdot5)=120$$

share|improve this question
3  
Can you tell me why you wrote "Where", with a capital initial "W" in "Where $\operatorname{rad}(n)$ is the radical"? I've seen lots of others do that --- so many that I have to suspect it's not merely a typo but rather that some people feels that's the right way to do it. Since it's not the beginning of a new sentence, but makes sense only as a continuation of the sentence already underway, I am puzzled. –  Michael Hardy Apr 28 at 18:05
3  
I don't know that I've ever seen this written out explicitly, but it's an immediate consequence of the multiplicativity of $\phi()$ along with the rule that $\phi(p^n)$ $= (p-1)p^{n-1}$ $= \phi(p)p^{n-1}$. –  Steven Stadnicki Apr 28 at 18:11
2  
Note that on the wikipedia totient page there is the formula $$\phi(mn)=\phi(m)\phi(n)\dfrac{(m,n)}{\phi((m,n))}$$ with $(m,n)$ denoting the GCD of $m$ and $n$... With just a little transformation, I believe this expresses your identity or nearly so. –  abiessu Apr 28 at 18:12
1  
@MichaelHardy: That's an irritating feature of the editor that gets me all the time. It seems like a sort of autocorrect or something. When you end a displayed math section with "$$" and hit enter, the shift key is enabled so the next letter typed is capitalized. I don't know if it's the site or my iPad doing this (probably the latter). It's especially irritating to try to type "$a+bi$" to find it has bee "corrected" to "$a+bI$" for some reason. –  MPW Apr 28 at 18:21
4  
(By the way, since I realized that my initial comment was a bit abrupt, I want to emphasize that I think it's awesome you're thinking about things this way and experimenting with formulae! You may be in well-trod ground here, but don't let that discourage you at all. There are unexplored wilds just down the road.) –  Steven Stadnicki Apr 28 at 18:35

3 Answers 3

up vote 6 down vote accepted

This is an interesting thing to notice, and you should be pleased.

As you guessed, and as Steven Stadnicki pointed out, this is not new; it follows quickly from two important properties of the $\phi$ function:

  1. $\phi(p^n) = (p-1)p^{n-1}$ when $p$ is prime
  2. $\phi(mn) = \phi(m)\phi(n)$ when $m$ and $n$ have no common factor

In particular, you suggested that your formula might be useful for calculating $\phi(n)$ for “large-ish $n$”, but observe that your formula requires knowing the radical of $n$, which is not in general any easier to find than the prime factorization of $n$. (And when the radical of $n$ is equal to $n$, as it is when $n$ is squarefree, your formula is no help at all.) But given $n = p_1^{a_1}\cdots p_k^{a_k}$ one has from (1) and (2) above that $$\begin{align} \phi(n) & = \phi\bigl(p_1^{a_1}\bigr)\cdots\phi\bigl(p_k^{a_k}\bigr) \\ & = (p_1-1)p_1^{a_1-1}\cdots (p_k-1)p_k^{a_k-1} \\ & = \frac{n}{p_1\cdots p_k}(p_1-1)\cdots(p_k-1) \\ & = n\left(\frac{p_1-1}{p_1}\right)\cdots \left(\frac{p_k-1}{p_k}\right) \tag{$\heartsuit$}\\ & = n\left(1-\frac1{p_1}\right)\cdots\left(1-\frac1{p_k}\right) \end{align}$$ which is well-known, and not significantly harder to compute (or perhaps easier) than your formula. The next-to last line ($\heartsuit$) is very similar to your formula.

share|improve this answer
7  
I would like to add that I hope I did not discourage you. You are doing real mathematics, and your claimed result is correct and sensible. –  MJD Apr 28 at 18:27
5  
What MJD said, exactly - don't let the fact that these may be familiar results discourage you at all; your exploration is absolutely to be commended. –  Steven Stadnicki Apr 28 at 18:36
2  
Thank you guys, that means a lot! I will definitely keep working at it, and maybe one day I'll discover something new. –  FofX Apr 28 at 18:42

Your identity can be written as $$ \frac{\phi(n)}{n}=\frac{\phi(\operatorname{rad}(n))}{\operatorname{rad}(n)} $$ In this form, it is obvious, because $$ \frac{\phi(m)}{m}=\prod_{p\mid m}\left(1-\frac1p\right) $$ and $n$ and $\operatorname{rad}(n)$ have exactly the same prime factors.

Still, a nice observation, well done!

share|improve this answer

$\newcommand{\rad}{\operatorname{rad}}$

Yes this is a bit of transformation of the euler product formula; it's correct since $$n=\prod_{i=1}p_i^{a_i}=p_1^{a_1}p_2^{a_2}p_3^{a_3}\cdots p_n^{a_n}\\ \rad(n)=p_1p_2p_3\cdots p_n\\\varphi(\rad(n))=(p_1-1)(p_2-1)(p_3-1)\cdots (p_n-1)\\ \frac{n}{\rad(n)}=p_1^{a_1-1}p_2^{a_2-1}p_3^{a_3-1}\cdots p_n^{a_n-1}\\ \varphi(\rad(n))\left(\frac{n}{\rad(n)}\right)=n\left(1-\frac{1}{p_1}\right)\left(1-\frac{1}{p_2}\right)\left(1-\frac{1}{p_3}\right)\cdots \left(1-\frac{1}{p_n}\right)$$ Which is all ready known

share|improve this answer

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.