Hello codeforces!

In one of the recent contests there appeared a problem which involved Euler's phi function, and I figured I could write a bit about this function here.

First, I will briefly introduce Euler's phi function, talk about two of its properties, and give you proofs of both of them. Ultimately, it will lead us to a way to compute the value of this function for some given integer $$$n$$$ with reasonable time complexity.