The Question about Euler's Totient Function : How phi(i*p) = p*phi(i)? Here, p is prime and p divides i, phi-> Euler totient function

85 Views Asked by At

I have a question about the Euler totient function. I am new to the number theory and i don't know where to start to prove this. If $p$ is prime and $p$ divides $i$,

$$ Φ (i\cdot p) = p \cdot Φ (i),$$

where $Φ (n)$ is Euler Totient Function.

I know as $p$ divides $i$, they($i$ and $p$) will not be co-prime so I can't apply multiplicative property here but I am unable to understand how this result came.

2

There are 2 best solutions below

0
On BEST ANSWER

An intuitive way of thinking of this is that, because $p$ divides $i$, the numbers counted in $\phi(i)$ are already coprime to $p$ (and thus to every power of $p$). So when you multiply by $p$, you retain all those coprime numbers in every block of $i$ numbers up to the new value $ip$, $\phi(i)$ coprime values in each of $p$ blocks; giving $\phi(ip) = p\cdot\phi(i)$.

0
On

If $p$ is prime and $n\in \Bbb Z^+$ then $\Phi (p^{n+1})=p^n(p-1)=\Phi (p^n)\cdot p.$

Let $0\ne i=jp^n$ where $j\in \Bbb Z$ and $n\in \Bbb Z^+$ and $p\not | \,j.$ Then $j, p^{n+1}$ are co-prime, and $j,p^n$ are also co-prime. So $$\Phi (ip)=\Phi (jp^{n+1})=\Phi (j)\cdot \Phi (p^{n+1})=\Phi (j)\cdot \Phi (p^n)\cdot p=\Phi (jp^n)\cdot p=\Phi (i)\cdot p.$$

The 2nd equality in the line above is because $j,p^{n+1}$ are co-prime. The 3rd is by my top line. The 4th is because $j,p^n$ are co-prime.

For a proof of the top line, consider that $\{m\in \Bbb Z^+: m\le p^n\land \gcd (m,p^n)>1\}=$ $\{m\in \Bbb Z^+: m\le p^n\land p|\,m\}=$ $\{pm':p^{n-1}\ge m'\in \Bbb Z^+\}$ is a set with $p^{n-1}$ members, so $\Phi (p^n)=p^n-p^{n-1}=p^{n-1}(p-1).$