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
    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
    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.
  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...)
Know someone interested in this topic? Share this thread via Reddit, Google+, Twitter, or Facebook

Similar Threads - Proof Euler's fuction Date
A Is the proof of these results correct? Jan 29, 2018
I Doubt about proof on self-adjoint operators. Nov 11, 2017
Euler Totient Property Proof Jun 28, 2012
Question from the proof in euler's forumla Mar 14, 2011
Euler's polynomial proof May 29, 2009