1.3: Problem 6: Show that every positive integer \(n\) has a unique expression of the form \(n = 2^rm\), \(r \geq 0\), \(m\) a positive odd integer.
Proof
We know that any integer \(n\) has a unique prime factorization. So \(n\) can be written as
$$
\begin{align*}
n = 2^{s} \cdot p_1^{n_1} \cdot p_2^{n_2} \cdots p_k^{n_k}
\end{align*}
$$
where \(s \in \mathbb{Z}_{\geq 0}\). \(p_1^{n_1},...p_k^{n_k}\) are the remaining prime factors. So now, let \(r = s\). If \(k = 0\), then let \(m = 1\). Otherwise, let \(m = p_1^{n_1} \cdot p_2^{n_2} \cdots p_k^{n_k}\). \(m\) is either 1 or a product of odd primes raised to some power so it’s always odd.
To show this expression is unique, suppose it wasn’t. Then \(n = 2^rm_1 = 2^sm_2\). for some \(r,s \in \mathbb{Z}\). However, prime factorization is unique and both \(m_1\) and \(m_2\) are odd positive integers. Therefore, we must have \(s = r\). So this means that \(m_1 = m_2\) as required. \(\ \blacksquare\)