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)
Thanks in advance
Edgar
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)$
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.