Skip to content
Technique

Counting distinct fractions by their lowest terms

Algebra • Binary and Other Number Systems

Statement

Every positive fraction has exactly one form in lowest terms, where and have no common factor other than . If and are taken from , cancelling only makes them smaller, so the lowest-terms form also has in that set. Hence the number of different values of equals the number of pairs from the set with no common factor.

How to use it

  1. 1Why it works: , and are one number. Keep only its lowest-terms form, , and each number is counted once.
  2. 2Go through the denominators one by one, and count the numerators that share no factor with .
  3. 3Remember : every counts, and gives the value once.

Worked example

How many different numbers can be made with ?

Step-by-step

  1. 1
    : , so values.

    Why: Every has no common factor with .

  2. 2
    : ; : ; : .

    Why: Drop each that shares a factor with , such as .

  3. 3

Answer

Watch out

Counting all pairs counts each repeated value many times: are all the single number .

Also known as

distinct values of p/q, fractions in lowest terms, coprime pairs count

Appears in past papers

2016 (II)