Derivation of Euler's formula for phi(m)

  • Thread starter Eus
  • Start date
  • #1
Eus
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.
 
Last edited:

Answers and Replies

  • #2
261
0
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.
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:
  • #3
Eus
94
0
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 [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]?
 
  • #4
261
0
this is a little bit long to prove

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

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 [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:
  • #5
Eus
94
0
Ah, I see.

Thank you very much for your help.
 

Related Threads for: Derivation of Euler's formula for phi(m)

  • Last Post
Replies
5
Views
11K
  • Last Post
Replies
3
Views
2K
  • Last Post
Replies
1
Views
5K
  • Last Post
Replies
11
Views
12K
  • Last Post
Replies
7
Views
2K
  • Last Post
Replies
13
Views
4K
  • Last Post
Replies
7
Views
5K
Replies
9
Views
3K
Top