What is the proof of Euler's function?

[SrEstroncio]

Hello.
I have been reading a book with an introductory section on number theory and the part regarding Euler's function just said that \varphi (n) = n-1 when n is prime and that \varphi (n) = n(1-\frac{1}{p_{1}})(1-\frac{1}{p_{2}})...(1-\frac{1}{p_{n}}) 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.

 

[dodo]

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.

 

[SrEstroncio]

No, it does not say anything about the value of \varphi (p^{\alpha}) but wikipedia saves the day. O was reading Wolfram's Mathworld's proof but I got lost around here:

Now let q be some other prime dividing m. The integers divisible by q are q, 2q, ..., (m/q)q. But these duplicate pq, 2pq, ..., (m/(pq))pq. So the number of terms that must be subtracted from \phi_p to obtain \phi_{pq} is

Here's the link.
http://mathworld.wolfram.com/TotientFunction.html

 

[dodo]

I also get a little confused, because the definition of \phi_p referred to the number of integers not divisible by p; while, when aiming at \phi_{pq}, 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. \phi is a multiplicative function, meaning that, for each pair of coprimes m, n, \phi(mn) = \phi(m) \phi(n). 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 \phi is multiplicative...)