Simple Fractions Symmetry


Given that k and n are positive integers, and kless thann, we shall call k/n a simple fraction if it cannot be cancelled.

For example, when n=9, there are exactly six simple fractions:


For a given denominator, ngreater than2, prove there will always be an even number of simple fractions.


For any given denominator, n, there will be nminus1 proper fractions:
1/n, 2/n, ... , (nminus1)/n.

If HCF(k,n)not equal1, it follows that nminusk will also share the same common factor. For example, HCF(8,28)=4 and as both 8 and 20 divide by 4, 20minus8=12 will also divide by 4. That is, if k/n cancels, (nminusk)/n will also cancel.

Using this idea, we can see how fractions will cancel in pairs. The exception is n being even, in which case there will be an odd number of proper fractions. However, the numerator of the middle fraction will be n/2, which will cancel.

For a given denominator, n, how many simple fractions exist?

Problem ID: 166 (Apr 2004)     Difficulty: 2 Star

Only Show Problem