- Thread starter
- #1

#### mathmaniac

##### Active member

- Mar 4, 2013

- 188

Please help me prove that the function E(x) is multiplicative,i.e.,

E(xy)=E(x).E(y)

- Thread starter mathmaniac
- Start date

- Thread starter
- #1

- Mar 4, 2013

- 188

Please help me prove that the function E(x) is multiplicative,i.e.,

E(xy)=E(x).E(y)

- Jan 26, 2012

- 644

[JUSTIFY]Assuming you want to prove it using only basic facts of numbers and not from the alternate definitions of the totient or using the CRT...

[HR][/HR]

Let's prove it for the case of two distinct primes first. Let $\varphi(p) = p - 1$ and $\varphi(q) = q - 1$. Now, choose any integer between $1$ and $pq - 1$. It can be either of four things:

1. a multiple of both $p$ and $q$

2. a multiple of $p$ but not of $q$

3. a multiple of $q$ but not of $p$

4. a multiple of neither

Now how many integers satisfy property $(1)$? Clearly there aren't any. The first one is $pq$ and it is too large.

How many satisfy property $(2)$? That is easy, the answer is $\frac{pq}{p} = q$ integers. (try doing it manually with small numbers to see why it works, this needs some justification but I am sure you can show that this is true)

How many satisfy property $(3)$? In the same way, $p$ integers.

Finally, what about $(4)$? It suffices to observe that every integer between $1$ and $pq - 1$ needs to fall into either one of those categories, so we must have $(1) + (2) + (3) + (4) = pq - 1$, that is, $(4) = (pq - 1) - (0 + p + q) = pq - (p + q) + 1 = (p - 1)(q - 1) = \varphi(p) \varphi(q)$. And $(4)$ contains $\varphi(pq)$ integers by definition.

Therefore, $\varphi(pq) = \varphi(p) \varphi(q)$ for distinct primes $p$, $q$.

[HR][/HR]

Then extend this proof to distinct coprime integers (not just primes) using a similar reasoning, and finally prime powers. Can you follow?[/JUSTIFY]

[HR][/HR]

Let's prove it for the case of two distinct primes first. Let $\varphi(p) = p - 1$ and $\varphi(q) = q - 1$. Now, choose any integer between $1$ and $pq - 1$. It can be either of four things:

1. a multiple of both $p$ and $q$

2. a multiple of $p$ but not of $q$

3. a multiple of $q$ but not of $p$

4. a multiple of neither

Now how many integers satisfy property $(1)$? Clearly there aren't any. The first one is $pq$ and it is too large.

How many satisfy property $(2)$? That is easy, the answer is $\frac{pq}{p} = q$ integers. (try doing it manually with small numbers to see why it works, this needs some justification but I am sure you can show that this is true)

How many satisfy property $(3)$? In the same way, $p$ integers.

Finally, what about $(4)$? It suffices to observe that every integer between $1$ and $pq - 1$ needs to fall into either one of those categories, so we must have $(1) + (2) + (3) + (4) = pq - 1$, that is, $(4) = (pq - 1) - (0 + p + q) = pq - (p + q) + 1 = (p - 1)(q - 1) = \varphi(p) \varphi(q)$. And $(4)$ contains $\varphi(pq)$ integers by definition.

Therefore, $\varphi(pq) = \varphi(p) \varphi(q)$ for distinct primes $p$, $q$.

[HR][/HR]

Then extend this proof to distinct coprime integers (not just primes) using a similar reasoning, and finally prime powers. Can you follow?[/JUSTIFY]

Last edited:

- Feb 13, 2012

- 1,704

The phi function is multiplicative, i.e. given two distict numers a and b, is...

Please help me prove that the function E(x) is multiplicative,i.e.,

E(xy)=E(x).E(y)

$$\varphi(a\ b) = \varphi(a)\ \varphi(b)\ (1)$$

... only if a and b are

$$ \varphi(n)= n\ \prod_{p|n} (1-\frac{1}{p})\ (2)$$

Kind regards

$\chi$ $\sigma$

- Thread starter
- #4

- Mar 4, 2013

- 188

Yeah,I understand.Then extend this proof to distinct coprime integers (not just primes) using a similar reasoning, and finally prime powers. Can you follow?

I also thought about that approach,but I was rather thinking of p^a and q^a or q^b and got lost somewhere.

Now I think I shouldn't have asked this.....

What does that mean?$$ \varphi(n)= n\ \prod_{p|n} (1-\frac{1}{p})\ (2)$$

Last edited:

- Feb 13, 2012

- 1,704

Because is...... what does that mean?...

$$ \varphi(n) = n\ \prod_{p|n} (1-\frac{1}{p})\ (1)$$

... it will be...

$$\varphi(a)\ \varphi(b) = a\ \prod_{p|a} (1-\frac{1}{p})\ b\ \prod_{p|b} (1-\frac{1}{p})\ (2)$$

... and You have $\varphi(a)\ \varphi(b) = \varphi(a\ b)$ only if the all prime factors of a are not prime factors of b...

Kind regards

$\chi$ $\sigma$

- Thread starter
- #6

- Mar 4, 2013

- 188

I mean what does the "pi-like" symbol means.I have seen it before,but I don't understand what it is.$$ \varphi(n) = n\ \prod_{p|n} (1-\frac{1}{p})\ (1)$$

.

Thanks

Last edited:

- Jan 26, 2012

- 644

It's like $\displaystyle \sum$ but a product instead. So for example:I mean what does the symbol "pi-like" symbol means.I have seen it before,but I don't understand what it is.

Thanks

$$\sum_{k = 1}^4 k^2 = 1^2 + 2^2 + 3^2 + 4^2$$

$$\prod_{k = 1}^4 k^2 = 1^2 \cdot 2^2 \cdot 3^2 \cdot 4^2$$

LaTeX code is \prod.

In chisigma's post the subscript $p \mid n$ under the product means "over all distinct primes $p$ which divide $n$". (the same notation can be used for sums)

- Thread starter
- #8

- Mar 4, 2013

- 188

What is it called?

- Jan 26, 2012

- 644

It's called a product operatorWhat is it called?

The symbol itself is the greek capital pi. Try typing \Pi in LaTeX: $\Pi$

More info here: Multiplication - Wikipedia, the free encyclopedia

- Thread starter
- #10

- Mar 4, 2013

- 188

....mean?$$ \varphi(n) = n\ \prod_{p|n} (1-\frac{1}{p})\ (1)$$

....and this.....

$$\varphi(a)\ \varphi(b) = a\ \prod_{p|a} (1-\frac{1}{p})\ b\ \prod_{p|b} (1-\frac{1}{p})\ (2)$$

- Jan 26, 2012

- 644

$$\varphi(n) = n \left [ \left ( 1 - \frac{1}{p_1} \right ) \left ( 1 - \frac{1}{p_2} \right ) \cdots \left ( 1 - \frac{1}{p_k} \right ) \right ]$$

- Thread starter
- #12

- Mar 4, 2013

- 188

hmm..,Thanks.

$$\varphi(n) = n \left [ \left ( 1 - \frac{1}{p_1} \right ) \left ( 1 - \frac{1}{p_2} \right ) \cdots \left ( 1 - \frac{1}{p_k} \right ) \right ]$$

I asked because the formula I had in mind for $$\varphi(n)$$ was $${p_1}^{{a_1}-1}({p_1}-1).{p_2}^{{a_2}-1}({p_2}-1)....{p_k}^{{a_k}-1}({p_k}-1)$$

for $$n={p_1}^{a_1}.{p_2}^{a_2}.....{p_k}^{a_k}$$

But

Last edited:

- Jan 26, 2012

- 644