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:

<br /> \varphi(m_{1}m_{2})=\varphi(m_{1})\varphi(m_{2})\mbox{ for coprime } m_{1} \mbox{ and } m_{2}<br />

The article proves that the multiplicative property holds in the following way:
Let 0 \leq n &lt; m be coprime to m.
Find remainders n_{1} and n_{2} of division of n by m_{1} and m_{2}, respectively:
<br /> n\equiv n_{1} \mbox{ (mod }m_{1}\mbox{) } \mbox{and } n\equiv n_{2} \mbox{ (mod } m_{2} \mbox{)}<br />
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:
<br /> 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}<br />
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:

<br /> \varphi(m_{1}m_{2})=\varphi(m_{1})\varphi(m_{2})\mbox{ for coprime } m_{1} \mbox{ and } m_{2}<br />

The article proves that the multiplicative property holds in the following way:
Let 0 \leq n &lt; m be coprime to m.
Find remainders n_{1} and n_{2} of division of n by m_{1} and m_{2}, respectively:
<br /> n\equiv n_{1} \mbox{ (mod }m_{1}\mbox{) } \mbox{and } n\equiv n_{2} \mbox{ (mod } m_{2} \mbox{)}<br />
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.