# 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:

For further reading, see the Wikipedia article on the totient function.