I read on http://www.cut-the-knot.org/blue/Euler.shtml that the derivation of the Euler's formula for [itex]\varphi(m)[/itex] requires that the following multiplicative property of [itex]\varphi[/itex] be established:(adsbygoogle = window.adsbygoogle || []).push({});

[tex]

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

[/tex]

The article proves that the multiplicative property holds in the following way:

Let [itex]0 \leq n < m[/itex] be coprime to [itex]m[/itex].

Find remainders [itex]n_{1}[/itex] and [itex]n_{2}[/itex] of division of [itex]n[/itex] by [itex]m_{1}[/itex] and [itex]m_{2}[/itex], respectively:

[tex]

n\equiv n_{1} \mbox{ (mod }m_{1}\mbox{) } \mbox{and } n\equiv n_{2} \mbox{ (mod } m_{2} \mbox{)}

[/tex]

Obviously, [itex]n_{1}[/itex] is coprime to [itex]m_{1}[/itex] and [itex]n_{2}[/itex] is coprime to [itex]m_{2}[/itex].

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

[tex]

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}

[/tex]

Is there any theorem that will guarantee that relationship?

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

Thank you.

**Physics Forums | Science Articles, Homework Help, Discussion**

Dismiss Notice

Join Physics Forums Today!

The friendliest, high quality science and math community on the planet! Everyone who loves science is here!

The friendliest, high quality science and math community on the planet! Everyone who loves science is here!

# Derivation of Euler's formula for phi(m)

**Physics Forums | Science Articles, Homework Help, Discussion**