Odd Number of Factors in Prime Factorization during Euler Function evaluation

717 Views Asked by At

I am trying to calculating $\phi(150)$

Prime factorization of $150 = 2\cdot3\cdot5^2$

So i can find $$\phi(150)= 150\cdot(1-\frac{1}{2})\cdot(1-\frac{1}{3})\cdot(1-\frac{1}{5})$$

So in case say on primefactoring three 2's come up

eg: $5\cdot2\cdot2\cdot2$ I think in prime factorization even numbers of factors is grouped together So in this case it becomes $5\cdot2\cdot2$

Is this right?

1

There are 1 best solutions below

2
On BEST ANSWER

When calculating $\phi(n)$, you consider each prime factor of $n$ once and only once regardless of how many times it "appears", if that's what you're asking. Of course, it must "appear" at least once (i.e. the exponent of the prime factor in the prime factorization of $n$ must be positive).

For example, $$\begin{align}\phi\left(2^{5}\cdot3^{4}\cdot5^{3}\cdot11^{2}\right) &=\left(2^{5}\cdot3^{4}\cdot5^{3}\cdot11^{2}\right)\left(1 - \frac{1}{2}\right)\left(1-\frac{1}{3}\right)\left(1-\frac{1}{5}\right)\left(1-\frac{1}{11}\right) \\ &= 9504000\end{align}$$