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 \geq 0\). We want to show that \(n = 2^rm\) where \(r \geq 0\) and \(m\) is odd. Hence, let \(r = s\). Now, if \(k = 0\), then we don’t have any remaining prime factors so let \(m = 1\). Otherwise, let

$$ \begin{align*} m = p_1^{n_1},...p_k^{n_k} \end{align*} $$

\(m\) is either \(1\) or a product of odd primes raised to some power. The product of odd numbers is odd and so \(m\) is odd.

To show uniqueness, suppose it wasn’t unique. Then

$$ \begin{align*} n = 2^rm_1 = 2^sm_2 \end{align*} $$

for some \(r,s \geq 0\) and \(m_1,m_2\) are positive odd integers. Without loss of generality, assume that \(r \leq s\). Then

$$ \begin{align*} m_1 = 2^{s-r}m_2 \end{align*} $$

Since \(m_2\) is odd, the right hand side is even unless \(s - r = 0\). Therefore, we must have that \(s = r\). But this implies that \(m_1 = m_2\). Hence, the representation \(n = 2^rm\) with \(m\) odd is unique. \(\ \blacksquare\)

References