1. ## is phi multiplicative

can somoene pls prrovide a complete proof that if (m1,m2) =1 then phi(m) is multiplicative?

and can someone pls provide me a method for computing phi(2004)

Edgar

2. 1. Given that $\displaystyle \sum_{d|n}\phi(d)=n$ by Möbius inversion formula we have that $\displaystyle n\cdot{\sum_{d|n}\frac{\mu(d)}{d}}=\phi(n)$ and since $\displaystyle \frac{\mu(n)}{n}$is multiplicative it follows that $\displaystyle n\cdot{\sum_{d|n}\frac{\mu(d)}{d}}=\phi(n)$ is multiplicative (if $\displaystyle f(n)$ is multiplicative then so is $\displaystyle \sum_{d|n}f(d)$)

Note also that $\displaystyle \sum_{d|n}\frac{\mu(d)}{d}=\prod_{p|n}\left(1-\frac{1}{p}\right)$ (where the product runs through the prime divisors of n)

Thus: $\displaystyle n\cdot{\prod_{p|n}\left(1-\frac{1}{p}\right)}=\phi(n)$

2. Consider the Inclusion-exclusion principle - Wikipedia, the free encyclopedia
and calculate $\displaystyle n-\phi(n)$, and from there find the formula for $\displaystyle \phi(n)$ and conclude that it's multiplicative

To calculate $\displaystyle \phi(2004)$ find the prime divisors of 2004, these are $\displaystyle 2,3$ and $\displaystyle 167$ thus: $\displaystyle 2004\cdot{\left(1-\frac{1}{2}\right)\left(1-\frac{1}{3}\right)\left(1-\frac{1}{167}\right)}=\phi(2004)$

3. ## is phi multiplicative

with regards caluclating phi(2004)

2004 = 2 x 2 x 3 x 167

is it a rule that you do not repeat the primes being used when usin the formula ie only use two once in the formula even though it appears twice?

4. Here is another proof.
Let $\displaystyle a$ be a positive integer. Define $\displaystyle X_a = \{ 1\leq x\leq a | \gcd( a,x)=1\}$.

We will prove that $\displaystyle |X_{nm}| = |X_n||X_m|$ if $\displaystyle \gcd(n,m)=1$.
Define $\displaystyle \phi: X_{nm} \mapsto X_n\times X_m$ as $\displaystyle (x\bmod n,x\bmod m)$. Where $\displaystyle \bmod n,\bmod m$ is reduction modolu $\displaystyle n$ and $\displaystyle m$.
Now use the Chinese Remainder Theorem to prove this is one-to-one and onto.