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
- 1Why it works: , and are one number. Keep only its lowest-terms form, , and each number is counted once.
- 2Go through the denominators one by one, and count the numerators that share no factor with .
- 3Remember : every counts, and gives the value once.
Worked example
How many different numbers can be made with ?
Step-by-step
- 1:
, so values. Why: Every has no common factor with .
- 2:
; : ; : . Why: Drop each that shares a factor with , such as .
- 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