Dismiss Notice
Join Physics Forums Today!
The friendliest, high quality science and math community on the planet! Everyone who loves science is here!

Proof of Euler's fuction.

  1. Jan 21, 2010 #1
    Hello.
    I have been reading a book with an introductory section on number theory and the part regarding Euler's function just said that [tex] \varphi (n) = n-1 [/tex] when n is prime and that [tex] \varphi (n) = n(1-\frac{1}{p_{1}})(1-\frac{1}{p_{2}})...(1-\frac{1}{p_{n}}) [/tex] when n is a composite number.
    The book (What is mathematics by Richard Courant) said the proof was "completely trivial" but that they wouldn't say it and I was wondering if someone could provide a proof or guide me through one.

    Thanks in advance.
     
    Last edited: Jan 21, 2010
  2. jcsd
  3. Jan 22, 2010 #2
    Hi,
    does the book say something about the value of phi when n is a power of a prime? That's a useful intermediate result.

    In general, you could use a second book. (Or wikipedia.)
    "Elementary number theory" by David Burton is a nice introduction.
     
  4. Jan 22, 2010 #3
    No, it does not say anything about the value of [tex] \varphi (p^{\alpha}) [/tex] but wikipedia saves the day. O was reading Wolfram's Mathworld's proof but I got lost around here:
    Here's the link.
    http://mathworld.wolfram.com/TotientFunction.html
     
  5. Jan 22, 2010 #4
    I also get a little confused, because the definition of [itex]\phi_p[/itex] referred to the number of integers not divisible by p; while, when aiming at [itex]\phi_{pq}[/itex], I believe they mean now integers coprime to pq (that is, not divisible by either p, or q, or both). When p was prime it was the same thing, but as pq is composite, the distinction must be made.

    For example, if you seek the number of integers (less than some limit) coprime to 6, you can discount the multiples of 2 and then discount the multiples of 3... but take in mind that you just discounted twice the multiples of 6.

    However, I would have imagined a shorter way to the proof. [itex]\phi[/itex] is a multiplicative function, meaning that, for each pair of coprimes m, n, [itex]\phi(mn) = \phi(m) \phi(n)[/itex]. Now, any number has a prime factorization (can be expressed as a product of prime powers), and any two of these prime powers are coprime.

    (Of course, then you should probably prove first that [itex]\phi[/itex] is multiplicative...)
     
Share this great discussion with others via Reddit, Google+, Twitter, or Facebook