0

I try to show that Euler's totient function is a multiplicative function. $$\varphi(nm)=\varphi(n)*\varphi(m)$$ with gcd(m,n)=1,But I don't understand why this happens

$$n = \prod_{k=1}^{z}p_{k}^{e_{k}}$$ $$\iff \varphi(n) = n \prod_{k=1}^{z}(1-\frac{1}{p_{k}})$$

especially, why does this happen? $\varphi(n) = n \prod_{k=1}^{z}(1-\frac{1}{p_{k}})$

R.R
  • 33
  • 6
  • 1
    Is it true for $n$ a prime? ... for $n$ a power of a prime? Do you have a relation for $\varphi(m,n)$ when $\gcd(m,n) = 1$? – Eric Towers Jan 16 '20 at 00:59

4 Answers4

1

Hint: Start by thinking about $\varphi$ of a prime power. Can you show that $\varphi(p^e)=p^{e-1}(p-1)$ ?

Now use the fact that $\varphi$ is multiplicative.

Donald Splutterwit
  • 36,613
  • 2
  • 26
  • 73
0

That formula can be thought of using a divisibility argument. If n is a product of primes and powers of primes, a number will be relatively prime to n iff it is not a multiple of any prime. The number of numbers less than n which are not a multiple of a prime is 1-1/p. Do this for all divisor of n, multiply, and multiply by the total numbers in our range, n, to get the final formula.

Abhishek Vangipuram
  • 366
  • I don't understand this'' The number of numbers less than n which are not a multiple of a prime is 1-1 / p.'' – R.R Jan 16 '20 at 01:29
0

If we put $N$ back in the product, we get: $$\prod _{p\mid N} (N-{N\over p})$$ but if $p$ divides $N$, for each term, this is the number of values less than $N$ that don't have a factor of all $p$ in them. We are simply weighting each value by the number of values that don't have a previous prime divisor of $N$ in them.

0

given a integer n, we know that n is a factor of primes such that $$n = p_{1}^{\alpha_{1}}...p_{z}^{\alpha_{z}} = \prod_{k=1}^{z}p_{k}^{\alpha_{k}}$$ then $$n \cdot m = p_{1}^{\alpha_{1}}...p_{z}^{\alpha_{z}} \cdot q_{1}^{\beta{1}}...q_{m}^{\beta{m}}$$ can be rearranged into a single prime factorization, because $n \cdot m \in \mathbb{Z} $

So i'll just call $n=nm = \prod_{k=1}^{z}p_{k}^{\alpha_{k}}$

We also know, that given any prime p, $$\varphi(p^{k}) = (p-1)p^{k-1}$$

Then, assuming $\varphi(n)$ is multiplicative, we get $$ \varphi(n) = \varphi(\prod_{k=1}^{z}p_{k}^{\alpha_{k}}) = \prod_{k=1}^{z}\varphi(p_{k}^{\alpha_{k}}) $$

Then, $$ \varphi(n \cdot m) = \varphi(\prod_{k=1}^{z}p_{k}^{\alpha_{k}}) \cdot \varphi(\prod_{k=1}^{m}q_{k}^{\beta{k}}) = \prod_{k=1}^{z}\varphi(p_{k}^{\alpha_{k}}) \cdot \prod_{k=1}^{m}\varphi(q_{k}^{\beta{k}}) $$

because $p_{k}$ is a prime for all k between 1 and z, $$ \prod_{k=1}^{z}\varphi(p_{k}^{\alpha_{k}}) = \prod_{k=1}^{z}(p_{k}-1)p_{k}^{\alpha_{k}-1} = \prod_{k=1}^{z}(1-\dfrac{1}{p_{k}})p_{k}^{\alpha_{k}}$$

$$\prod_{k=1}^{z}(1-\dfrac{1}{p_{k}})p_{k}^{\alpha_{k}} = \prod_{k=1}^{z}p_{k}^{\alpha_{k}} \prod_{k=1}^{z}(1-\dfrac{1}{p_{k}})$$

And recalling our definition of n = $\prod_{k=1}^{z}p_{k}^{\alpha_{k}}$, $$\varphi(n) = n \prod_{k=1}^{z}(1-\frac{1}{p_{k}}) $$

Thus $\varphi(n*m) = \varphi(n) * \varphi(m) \implies \varphi(n) = n\prod_{k=1}^{z}(1-\frac{1}{p_{k}})$

If you assume the fact that $\varphi(n) = n \prod_{k=1}^{z}(1-\frac{1}{p_{k}})$ is true, you can do the opposite procedure and arrive in the conclussion that $\varphi(n)$ is multiplicative

Thus, $$\varphi(n \cdot m) = \varphi(n) \cdot \varphi(m) \iff \varphi(n) = n\prod_{k=1}^{z}(1-\frac{1}{p_{k}})$$

LucasG
  • 1
  • you can also prove that $\varphi(n)$ is multiplicative using the fact that given n,m such that $gcd(n,m)=1$, $gcd(a,nm) = 1 \iff gcd(a,n) = 1 \text{ and } gcd(a,m) = 1$ – LucasG Oct 31 '23 at 21:56