A Formula for φ
We would like to develop a formula for Euler’s φ function so that we can apply Euler’s Theorem in practice. This video states simply what we are trying to accomplish, which is to look at two special cases.
General Formulas for φ(p2) and φ(pq)
This video explores a derivation for the special cases φ(p2) and φ(pq), and compares our results for our two formulas.
A Visual Representation of Our Proof
Another way of understanding our proof for φ(p2) and φ(pq) is to represent how we counted the multiples of p and q with a Venn diagram. We will have some work to do in order to derive a more general result for φ; we will need to take a slight detour through the Chinese Remainder Theorem in order to arrive at a general expression.