# Number TheoryNo. of numbers relatively prime to a number

#### mathmaniac

##### Active member
Let E(x) denote the number of numbers relatively prime to x.
E(xy)=E(x).E(y)

#### Bacterius

##### Well-known member
MHB Math Helper
[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
Let E(x) denote the number of numbers relatively prime to x.
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
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
... 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
$$\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
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
What is it called?

MHB Math Helper

#### mathmaniac

##### Active member
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
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
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
[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]