Welcome to our community

Be a part of something great, join today!

Number Theory No. of numbers relatively prime to a number

mathmaniac

Active member
Mar 4, 2013
188
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

Well-known member
MHB Math Helper
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]
 
Last edited:

chisigma

Well-known member
Feb 13, 2012
1,704
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

Active member
Mar 4, 2013
188
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?
 
Last edited:

chisigma

Well-known member
Feb 13, 2012
1,704
... 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

Active member
Mar 4, 2013
188
$$ \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
 
Last edited:

Bacterius

Well-known member
MHB Math Helper
Jan 26, 2012
644
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

Active member
Mar 4, 2013
188
What is it called?
 

Bacterius

Well-known member
MHB Math Helper
Jan 26, 2012
644

mathmaniac

Active member
Mar 4, 2013
188
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

Well-known member
MHB Math Helper
Jan 26, 2012
644
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

Active member
Mar 4, 2013
188
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.
 
Last edited:

Bacterius

Well-known member
MHB Math Helper
Jan 26, 2012
644
[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]