Past exam of the mathematics course of the University of Cambridge 2008 ia Paper 4 2D b Solution 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 .