Dismiss Notice
Join Physics Forums Today!
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)

  1. Jan 12, 2008 #1


    User Avatar

    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:

    \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 [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:
    n\equiv n_{1} \mbox{ (mod }m_{1}\mbox{) } \mbox{and } n\equiv n_{2} \mbox{ (mod } m_{2} \mbox{)}
    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:
    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 [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: Jan 12, 2008
  2. jcsd
  3. Jan 12, 2008 #2
    the remainder [itex]n_{1}[/itex] is coprime to [itex]m_{1}[/itex] and the remainder [itex]n_{2}[/itex] is coprime to [itex]m_{2}[/itex] because otherwise the division of [itex]n_{1}[/itex] by [itex]m_{1}[/itex] and [itex]n_{2}[/itex] by [itex]m_{2}[/itex] should give another remainders, and in these cases we cannot call [itex]n_{1}[/itex] and [itex]n_{2}[/itex] 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.
    Last edited: Jan 12, 2008
  4. Jan 15, 2008 #3


    User Avatar

    Ah, thank you for the explanation.

    But, 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]?
  5. Jan 15, 2008 #4
    this is a little bit long to prove

    for a p prime, [itex]\varphi(p^a) = p^{a-1}(p-1)[/itex]


    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 [itex]p^{a-1}[/itex] integers between 1 and [itex]p^a[/itex] which are divisible by p: p, 2p, 3p, 4p, 5p, ..., [itex]p^{a-1}p[/itex]

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

    from here one can use this result to prove that relation

    to prove the relation [tex]\varphi(m_{1}m_{2})=\varphi(m_{1})\varphi(m_{2})\ box{ for coprime } m_{1} \mbox{ and } m_{2}[/tex] I think you can search the web and find probably the same proof that I have here from a book
    Last edited: Jan 15, 2008
  6. Jan 17, 2008 #5


    User Avatar

    Ah, I see.

    Thank you very much for your help.
Share this great discussion with others via Reddit, Google+, Twitter, or Facebook