## Simple Fractions Symmetry

#### Problem

Given that `k` and `n` are positive integers, and `k``n`, 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, `n`2, prove there will always be an even number of simple fractions.

#### Solution

For any given denominator, `n`, there will be `n`1 proper fractions:

1/`n`, 2/`n`, ... , (`n`1)/`n`.

If HCF(`k`,`n`)1, it follows that `n``k` 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, (`n``k`)/`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?