- #1

- 94

- 0

## Main Question or Discussion Point

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:

[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.

[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.

Last edited: