mathschallenge.net

Problem

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

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

1/92/94/95/97/98/9

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

Solution

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

If HCF(k,n)1, it follows that nk will also share the same common factor. For example, HCF(8,28)=4 and as both 8 and 20 divide by 4, 208=12 will also divide by 4. That is, if k/n cancels, (nk)/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?