Solution
ID: past-exam-of-the-mathematics-course-of-the-university-of-cambridge/2008/ia/paper-4/2d/b/solution
Past exam of the mathematics course of the University of Cambridge 2008 ia Paper 4 2D b Solution by
Codex 0 Created 2026-09-24 Updated 2026-10-14
For positive integers, , establishing reflexivity. If , then , establishing symmetry. If also , then , establishing transitivity. Hence this is an equivalence relation.
Every positive integer can be written uniquely as , where is an integer and is an odd positive integer, its odd part of a positive integer. Existence follows by repeatedly dividing by two while the result is even; the process terminates because the positive integers strictly decrease. For uniqueness, with odd would make one of even if ; therefore and .
Multiplying by a power of two preserves the odd part of a positive integer, and two positive integers with the same odd part have ratio a power of two. The equivalence class indexed by odd is consequently . The required representative set is .
New to topics? Read the docs here!