The Euler phi function \(\phi(n)\) counts the number of integers in \( \{1,2,\ldots,n\}\) that are coprime to \(n\). For example \(\phi(9)=6\) because in the set \(\{1,2,3,4,5,6,7,8,9\}\), there are 6 integers that are coprime to 9. Those integers being \(1\), \(2\), \(4\), \(5\), \(7\) and \(8\).
Let \(a\) be some positive integer and let \(p\) be a prime. We need to find a formula for \(\phi (p^a)\). Thats means we need to find a formula for the number of integers in the set \(\{1,2,\ldots,p^a\}\) that are coprime to \(p^a\).
For \(\phi(p)\), the formula is simple, it's \(\phi(p)=p-1\), because every integer in \(\{ 1,2,\ldots,p \} \) other than \(p\) itself is coprime to \(p\). Now consider the set below, where \(n\) is some positive integer:
How many integers are coprime to \(p\)? According to this lemma, if \((p,i)=1\), then \((p,kp+i)=1\), where \(i\) and \(k\) are any positive integers. For example, if \((p,2)=1\), then \((p,p+2)=1\) and \((p,2p+2)=1\). The same argument can be applied to every integer after \(2p\) and below \(3p\). Every integer shown here, other than the ones in the last row, are coprime to \(p\):
Now let \(n=p^{a-1}\):
All of the integers above, except for the ones in the last row are coprime to \(p\). According to this lemma, if \((p,i)=1\), then \((p^2,i)=1\). By repeated reapplying this rule, we can say \((p^a,i)=1\). This means all of the integers above, except for the ones in the last row are also coprime to \(p^a\). As for the last row, since all the integers are divisible by \(p\), and since \(p^a\) is divisible by \(p\) as well, then \(p^a\) is not coprime to any of them.
So how many integers are coprime to \(p^a\)? Consider the table of numbers above. There are \(p-1\) integers in every column if you exclude the last row, and there are \(p^{a-1}\) columns in total. This means the total number of integers that are coprime to \(p^a\) is \([(p-1) * p^{a-1}]\). Therefore: