Back in the days when I was in the final year of obtaining the Bachelor's degree, we had an amazing professor, Dr. Narsimhan. He had founded the Maths Club. After the regular lectures, all the math professors gathered in a class room & discussed any random interesting math topic that struck them. The club was open to anybody who was interested to attend.
It was one of those Math Club lectures where we were solving some problems from IIT Math Olympiad question papers. Dr. Narsimhan had moved on to some other college, by then. While solving one such problem, we had a situation where we needed to find number of numbers that are coprime to 10,000. If you are new to co-primes, here are some interesting links to read about them here.
To explain it in a couple of lines, two numbers are co-prime if their g.c.d is 1.
Eg: Greatest Common Divisor of 15 & 8 is 1. Hence 15 & 8 are co-prime. How many numbers less than 15 are co-prime to 15? In other words, how many numbers, less than 15 have a gcd of 1 relative to 15?
Lets see :

From the picture above, we find that numbers (yellow background) 1, 2, 4, 7, 8, 11, 13, 14 have gcd of 1 relative to 15. So we say, 1, 2, 4, 7, 8, 11, 13, 14 are all co-prime to 15.
How many are they?
There are 8 numbers, in all, that are co-prime to 15. Symbolically, we write this as phi(15) = 8 or

Going back to finding the co-prime of 10000, we did not have a ready answer then & the question remained un-answered. The question haunted me on my way back home. Not able to resist the temptation to find the answer, I worked out a few examples & stumbled upon a formula to find the number of co-primes for any given number. I had a fair understanding of how far Mathematics had advanced by then, and I felt sure this formula would have been already discovered. Nonetheless, I was excited about the discovery. An year later, I learnt that this formula was first discovered by Euler, and it is called Euler's Totient function. Though Euler had proved this using more sophisticated methods, I happened to work it out using more trivial methods.

Lets go through a couple of examples, before we try our hands at the proof.
Example: Lets say we have to find the number of numbers co-prime to 144. Or, in other words, we have to find phi(144).
Lets see how we can do that. We can write factor 144 as 2 x 2 x 2 x 2 x 3 x 3. Or, expressing in terms of powers of primes, 144 = 2^4 x 3^2.
Here, the numbers 2 & 3 are primes. In other words, to express 144 as a product of its prime factors, we only have to use the primes 2 & 3. Now, this is a significant observation, in order to reach our final formula. Next, we write 144 as an array of numbers, having 2 x 3 = 6 rows & 24 columns. (Note: 6 x 24 = 144). The idea is depicted in the picture below.

The last number in the first column is 6 (which is 2x3).
What are the numbers co-prime to 6, in the first column? They are 1 & 5.
Lets move over to the second column.
The last number is 12, which is 6x2.
What are the numbers in the second column, co-prime to 12? They are 7 & 11.
Similarly, if we continue the process, we find that the numbers in the first row, viz. 1,7,13, etc... are all co-prime to the numbers at the end of the respective columns. Also, the numbers in the 5 th row, 5,11,17,etc... are all co-prime to the numbers at the end of the respective columns.
Lets highlight the 2 rows.

Now, note that, if a number is co-prime to 6, it is also coprime to 144. If any number is coprime to 12, it is also co-prime to 144. A number that is co-prime to 18, is also co-prime to 144.
Which means, any number that is co-prime to ANY MULTIPLE of 6, is also co-prime to 144.
Knowing this, looking at the picture above, all numbers in the highlighted row are co-prime to 144.
Now, how many are they? There are 2 in each column. And there are 24 columns in all. Hence there are 24 x 2 = 48 numbers co-prime to 144.
That is, phi(144) = 48.
Cool! Following the process described above, we were able to find phi(144).
Now let try to find find phi(10000) using the same process.
First, lets write 10000 in terms of its prime factors : 10000 = 2^4 x 5^4.
The only unique primes needed to express 10000 as a product of primes is 2 and 5.
Next, lets make an array of 2x5=10 rows and 1000 columns, as in picture below.

Now, the last number in the first column is 10.
How many numbers in the first column are co-prime to 10? Thats easy, 4 numbers viz. 1,3,7,9.
The last number in the second column is 20.
How many numbers in the second column are co-prime to 20? Again, 4 numbers viz. 11,13,17,19.
Continuing this process, we find that all numbers in the 1st, 3rd, 7th & 9th row are co-prime to the last number in that column.
Lets highlight these rows.

Now, all these numbers are also co-prime to 10000.
Lets count them. 4 in every column & there are 1000 columns. Hence there are 4000 such numbers, all of which are co-prime to 10000.
So there's the answer we were trying to find - phi(10000) = 4000. :-)
Thats even cooler. Using this process, we were able to find Phi(10000) under a minute!

So how do these examples lead us to the general formula? Lets work out.
From first example,
phi(144) = Number of columns * phi (6), which is
     = 24 * phi(6)
     = (2^3 * 3^1) * phi(2 x 3)
That is,
phi(2^4 * 3^2) = (2^3 * 3^1) * phi(2 x 3)
So, we keep only one power of prime factors within the phi() and take out remaining ones.
Lets see if we come across the same pattern in 2nd example,
phi(10000) = Number of columns * phi (10)
     = 1000 x phi(2 x 5)
     = (2^3 * 5^3) * phi(2 x 5)
Hence,
phi(2^4 * 5^4) = (2^3 * 5^3) * phi(2 x 5)
Which follows the same pattern as above.

We can thus generalize the formula as
phi (p1^n1 * p2^n2 * p3^n3 ... pk^nk) = [ p1^(n1-1) * p2^(n2-1) * ... * pk^(nk-1) ] * phi (p1 * p2 * p3 * ... * pk)
The formula can be further simplified, as we will see below.

What we saw so far, were examples based on the actual working out of the proof.
I am tempted to post the actual proof, but the proof just follows the same steps as above and we run into numerous symbols that would not be of much interest to a reader who is just seeking some mathematical entertainment. However, I am posting here the generalized theorem & the generalized result.
What follows is derivation of Euler's Totient function based on the generalized result.

Theorem :
The number of numbers co-prime to a number n, whose prime factorization is

denoted by
is equal to

It can be further shown that

Proof:
The first part of the proof follows the same steps as shown in the examples above. The first part of the proof is being omitted, for the sake of keeping this discussion short. However, here's the derivation of the second part of the theorem, which leads us to the Euler's Totient function.
From above, we have proved that,
phi(n)= p1^(k1-1).p2^(k2-1)...pm^(km-1).phi(p1.p2...pm) ---- (1)
It is known that the function phi() is multiplicative.
That is, if a & b are coprime, then phi(a.b) = phi(a).phi(b) ---- (2)
From (1) & (2), since p1,p2...pm are all primes,
phi(p1.p2...pm) = phi(p1).phi(p2)...phi(pm) ---- (3)
Now, if p is a prime, then ALL numbers less than p are co-prime to p.
Which means, phi(p) = p-1
Using the above result in (3), we get
phi(p1.p2...pm) = (p1-1).(p2-1)...(pm-1) ----- (4)
Using (4), equation (1) becomes.
phi(n) = p1^(k1-1).p2^(k2-1)...pm^(km-1).(p1-1).(p2-1)...(pm-1)
Re-arranging the terms, we get
phi(n) = (p1-1)p1^(k1-1).(p2-1)p2^(k2-1)...(pm-1)pm^(km-1)
Which is nothing but Euler's Totient function.

Phew! That required some work, didnt it. If you are reading this line, then apparently, you havent dozed off yet.
Thanks! :-) I intend to post the first part of the proof, that I have omitted here, in a short while. However, if you are interested in knowing about it, feel free to write to me & I would be more than glad to share it with you.