Decomposition into Product of Power of 2 and Odd Integer is Unique
Theorem
Let $n \in \Z$ be an integer.
Then $n$ can be decomposed into the product of a power of $2$ and an odd integer.
Proof
Aiming for a contradiction, suppose there exists $n \in \Z$ which can be decomposed into a power of $2$ and an odd integer in more than one way.
That is:
- $n = 2^a r$
and:
- $n = 2^b s$
where:
- $a, b \in \Z_{\ge 0}$
- $r$ and $s$ are odd integers.
- either $a \ne b$ or $r \ne s$.
Suppose $r = s$.
Then:
- $\dfrac n r = \dfrac n s = 2^a = 2^b$
which leads to:
- $a = b$
which contradicts our supposition that either $r \ne s$ or $a \ne b$.
Similarly, suppose $a = b$.
Then:
- $\dfrac n {2^a} = \dfrac n {2^b} = r = s$
which also contradicts our supposition that either $r \ne s$ or $a \ne b$.
Thus both $r \ne s$ and $a \ne b$.
Without loss of generality, let $a > b$.
Then $2^{a - b} = 2^c$ where $c \ge 1$.
Thus:
- $\dfrac n {2^b} = 2^c r = s$
which means $s = 2 u$ for some $u \in \Z$.
Thus $s$ is an even integer.
This contradicts our supposition that $r$ and $s$ are both odd.
All possibilities have been investigated:
- $a = b, r \ne s$
- $a \ne b, r = s$
- $a \ne b, r \ne s$
All have been shown to lead to a contradiction.
Thus by Proof by Contradiction it can be seen that an decomposition of $n$ into the product of a power of $2$ and an odd integer is unique.
Hence the result.
$\blacksquare$
Sources
- 1971: George E. Andrews: Number Theory ... (previous) ... (next): $\text {2-4}$ The Fundamental Theorem of Arithmetic: Exercise $2$