# Proof of Euler's fuction.

1. Jan 21, 2010

### 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.

Last edited: Jan 21, 2010
2. Jan 22, 2010

### 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.

3. Jan 22, 2010

### 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:
http://mathworld.wolfram.com/TotientFunction.html

4. Jan 22, 2010

### 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...)