Derivation of Euler's formula for phi(m)

[Eus]

I read on http://www.cut-the-knot.org/blue/Euler.shtml that the derivation of the Euler's formula for $\varphi(m)$ requires that the following multiplicative property of $\varphi$ be established:

$$\varphi(m_{1}m_{2})=\varphi(m_{1})\varphi(m_{2})\mbox{ for coprime } m_{1} \mbox{ and } m_{2}$$

The article proves that the multiplicative property holds in the following way:
Let $0 \leq n < m$ be coprime to $m$.
Find remainders $n_{1}$ and $n_{2}$ of division of $n$ by $m_{1}$ and $m_{2}$, respectively:
$$n\equiv n_{1} \mbox{ (mod }m_{1}\mbox{) } \mbox{and } n\equiv n_{2} \mbox{ (mod } m_{2} \mbox{)}$$
Obviously, $n_{1}$ is coprime to $m_{1}$ and $n_{2}$ is coprime to $m_{2}$.

Although it says "obviously", I don't find that the relationship is obvious enough. That is:
$$n \mbox{ is coprime to } m\mbox{ and }m=m_{1}m_{2},\ m_{1} \mbox{ is coprime to } m_{2} }\mbox{ and }n\equiv n_{1} \mbox{ (mod }m_{1}\mbox{) } \rightarrow n_{1} \mbox{ is coprime to } m_{1}$$
Is there any theorem that will guarantee that relationship?

Besides that, why is the value of $\varphi(m_{1}m_{2})$ found by multiplying $\varphi(m_{1})$ and $\varphi(m_{2})$ instead of by adding $\varphi(m_{1})$ and $\varphi(m_{2})$?

Thank you.

 

[al-mahed]

I read on http://www.cut-the-knot.org/blue/Euler.shtml that the derivation of the Euler's formula for $\varphi(m)$ requires that the following multiplicative property of $\varphi$ be established:

$$\varphi(m_{1}m_{2})=\varphi(m_{1})\varphi(m_{2})\mbox{ for coprime } m_{1} \mbox{ and } m_{2}$$

The article proves that the multiplicative property holds in the following way:
Let $0 \leq n < m$ be coprime to $m$.
Find remainders $n_{1}$ and $n_{2}$ of division of $n$ by $m_{1}$ and $m_{2}$, respectively:
$$n\equiv n_{1} \mbox{ (mod }m_{1}\mbox{) } \mbox{and } n\equiv n_{2} \mbox{ (mod } m_{2} \mbox{)}$$
Obviously, $n_{1}$ is coprime to $m_{1}$ and $n_{2}$ is coprime to $m_{2}$.

Although it says "obviously", I don't find that the relationship is obvious enough.

the remainder $n_{1}$ is coprime to $m_{1}$ and the remainder $n_{2}$ is coprime to $m_{2}$ because otherwise the division of $n_{1}$ by $m_{1}$ and $n_{2}$ by $m_{2}$ should give another remainders, and in these cases we cannot call $n_{1}$ and $n_{2}$ remainders. For instance if a = qb + r, r being the remainder, then by definition r < b (otherwise the division of r by b should let another remainder, and then r shouldn't be a the remainder). So, if a = qb + r, r being the remainder, b and r are always coprimes.

 

[Eus]

So, if a = qb + r, r being the remainder, b and r are always coprimes.

Ah, thank you for the explanation.

But, why is the value of $\varphi(m_{1}m_{2})$ found by multiplying $\varphi(m_{1})$ and $\varphi(m_{2})$ instead of by adding $\varphi(m_{1})$ and $\varphi(m_{2})$?

 

[al-mahed]

this is a little bit long to prove

for a p prime, $\varphi(p^a) = p^{a-1}(p-1)$

proof:

for every prime number, the amount of number from 1 to p such that all of them are coprimes with p is = p-1. Ex: p = 7 ==> 6,5,4,3,2,1 are coprime with 7

there are $p^{a-1}$ integers between 1 and $p^a$ which are divisible by p: p, 2p, 3p, 4p, 5p, ..., $p^{a-1}p$

thus the set {1,2,3,4,...,$p^a$} contain exactly $p^a - p^{a-1} = p^{a-1}(p-1)$ integers which are relatively prime to $p^a$

from here one can use this result to prove that relation

to prove the relation $$\varphi(m_{1}m_{2})=\varphi(m_{1})\varphi(m_{2})\ box{ for coprime } m_{1} \mbox{ and } m_{2}$$ I think you can search the web and find probably the same proof that I have here from a book

 

[Eus]

Ah, I see.

Thank you very much for your help.