Solution

ID: past-exam-of-the-year-1-of-the-computer-science-course-of-the-university-of-oxford/2016/discrete-mathematics-continuous-mathematics-and-probability-resit/2/b/solution

For positive integer pairs, reflexivity is . If , reversing the equality gives , establishing symmetry. For transitivity, suppose and . Then and , whence
Since , cancellation gives . Thus , and is an equivalence relation.
Membership in the equivalence class of means , or . Since and are coprime, and for a positive integer . Conversely every such pair satisfies the equality. Therefore
These pairs are precisely the positive numerator-denominator representations of the rational number .

New to topics? Read the docs here!