Counting simplified fractions

We all know that many fractions can be simplified, for example, 6/20 may be better written as 3/10. So how many fractions (less than 1) really use a denominator of 20? The answer turns out to be exactly eight… 1/20, 3/20, 7/20, 9/20, 11/20, 13/20, 17/20, and 19/20. But is there a rhyme or reason to this answer?

Mathematicians have given a name for the quantity we are talking about. For any number $n$, we let $\phi_n$ be the number of simplified fractions (less than 1) with a denominator of $n$. Knowing its values is important in subjects like number theory and cryptography. In this investigation we explored the pattern of values of $\phi_n$.

We quickly realized that if $n$ is a prime number, then it is easy to find $\phi_n$. We then advanced to the cases when $n$ is a power of a prime, or a product of several distinct primes. Eventually, we developed a method to calculate $\phi_n$ for any $n$.

A plot of the $\phi_n$ sequence reveals its complexity as well as some striking patterns:
731px-EulerPhi.svg

Wikipedia article on the totient function

Our handout