Euler's function

Euler's function is given by

For any , Proof:
Let . From the definition of we then have Our goal now is to show that , so we construct a bijection . We define for every , which is well-defined since , and since , we also have . We now show injectivity. If we have and since and are coprime we have and , so is injective. Finally we show surjectivity. Let , and let . Then let and . and must then be coprime, by the maximality of . We also have since , so , and we have so is also surjective, hence a surjection.

Let such that and whose prime factorization is Then Proof:
Let . Then we have . A general intersection of these is , which thus contains multiples of , which there are of. So we have which can be verified is equal to the statement by carrying out the multiplications.