Number Theory No. of numbers relatively prime to a number

[mathmaniac]

Let E(x) denote the number of numbers relatively prime to x.
Please help me prove that the function E(x) is multiplicative,i.e.,
E(xy)=E(x).E(y)

 

[Bacterius]

[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]

 

[chisigma]

Let E(x) denote the number of numbers relatively prime to x.
Please help me prove that the function E(x) is multiplicative,i.e.,
E(xy)=E(x).E(y)

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

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

... only if a and b are relatively prime or, in other words, is MCD (a,b)=1. The prove of that is easily derivable by the explicit expression...

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

Kind regards

$\chi$ $\sigma$

 

[mathmaniac]

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

Yeah,I understand.
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.....

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

What does that mean?

 

[chisigma]

... what does that mean?...

Because is...

$$ \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$

 

[mathmaniac]

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

.

I mean what does the "pi-like" symbol means.I have seen it before,but I don't understand what it is.

Thanks

 

[Bacterius]

I mean what does the symbol "pi-like" symbol means.I have seen it before,but I don't understand what it is.

Thanks

It's like $\displaystyle \sum$ but a product instead. So for example:
$$\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)

 

[mathmaniac]

What is it called?

 

[Bacterius]

What is it called?

It's called a product operator

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

More info here: Multiplication - Wikipedia, the free encyclopedia

 

[mathmaniac]

So what does this....

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

....mean?

....and this.....

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

 

[Bacterius]

The first one means that if $n = p_1 p_2 \cdots p_k$ with $p_i$ a distinct prime, then:
$$\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 ]$$

 

[mathmaniac]

The first one means that if $n = p_1 p_2 \cdots p_k$ with $p_i$ a distinct prime, then:
$$\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 ]$$

hmm..,Thanks.

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 chisigma's formula is about distinct primes,right?I think it cannot be modified for non-distinct primes too...because of the common factor.

 

[Bacterius]

[JUSTIFY]Yes, that is kind of the idea. The totient formula is only multiplicative for coprime integers (which do not have common factors). When you multiply two integers which have a common factor, the totient of the product isn't the product of the totients, so the question doesn't apply in this case. You want to (and can only) show the totient is multiplicative only for numbers which share no common prime factors (in general) [/JUSTIFY]