is phi multiplicative

**edgar davids** · May 14th 2008, 03:36 AM

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

**PaulRS** · May 14th 2008, 04:22 AM

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

Note also that $\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: $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 $n-\phi(n)$ , and from there find the formula for $\phi(n)$ and conclude that it's multiplicative

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

**edgar davids** · May 14th 2008, 05:44 AM

thanks for your response.

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?

**ThePerfectHacker** · May 14th 2008, 07:22 AM

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

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

Thread: is phi multiplicative

LinkBack

Thread Tools

Display

is phi multiplicative

is phi multiplicative

Similar Math Help Forum Discussions

Multiplicative inverse 71.7

GCD Multiplicative Property

multiplicative

Multiplicative Set

Multiplicative inverse

Search Tags