[Math] Expression of an Integer as a Power of 2 and an Odd Number (Chartrand Ex 5.4.2[a])

elementary-number-theory

Let $n$ be a positive integer. Show that every integer $m$ with $ 1 \leq m \leq 2n $ can be expressed as $2^pk$, where $p$ is a nonnegative integer and $k$ is an odd integer with $1 \leq k < 2n$.

I wrote out some $m$ to try to conceive the proof. I observed:

$\bbox[5px,border:1px solid grey]{\text{Case 1: $m$ odd}}$ Odd numbers $\neq 2p$, thus the only choice is to put $p = 0$ and $k = m$.

$\bbox[5px,border:1px solid grey]{\text{Case 2: $m$ even and power of 2}}$ Then $p$ can be determined by division or inspection to "square with" the power of $2$. This requires $k = 1$. Is an explicit formula for $p$ necessary?

$\bbox[5px,border:1px solid grey]{\text{Case 3: $m$ even and NOT A power of 2}}$

$\begin{array}{cc}
\\
\boxed{m = 6}: 6 = 2^1 \cdot 3 \qquad \qquad & \boxed{m = 10}: 10 = 2^1 \cdot 5 \qquad \qquad & \boxed{m = 12}: 12 = 2^2 \cdot 3 \\
\boxed{m = 14}: 14 = 2 \cdot 7 \qquad \qquad & \boxed{m = 18}: 18 = 2^1 \cdot 9 \qquad \qquad & \boxed{m = 20}: 20 = 2^2 \cdot 5\\
\boxed{m = 22}: 22 = 2 \cdot 11 \qquad \qquad & \boxed{m = 24}: 24 = 2^3 \cdot 3 \qquad \qquad & \boxed{m = 26}: 26 = 2^1 \cdot 13
\end{array}$

Solution's Proof by Contradiction: $\color{#0073CF}{\Large{\mathbb{[}}}$Let $p$ be the greatest nonnegative integer
such that $2^p | m. \color{#0073CF}{\Large{\text{]}}}$ $\color{red}{\Large{\text{[}}}$ Then $m= 2^pk$ for some positive integer $k$. Necessarily $k$ is odd,
for otherwise this would contradicts the definition of $p$. $\color{red}{\Large{\text{]}}}$

$\Large{\text{1.}}$ Could someone please expound on the answer? It differs from my work above?

$\Large{\text{2.}}$ Is there a general formula/pattern for Case $3$?

I referenced 1. Source: Exercise 5.42(a), P125 of Mathematical Proofs, 2nd ed. by Chartrand et al

Best Answer

I am not sure, what you are looking for as the proof is fine, but here are some alternatives:

  • You could use unique prime factoritzation, so for any $m$, there are $k_i\geq 0$, such that: $$m=2^{k_0}\cdot 3^{k_1}\cdot 5^{k_2}\cdot \dots$$ Then $p=k_0$ and $k=3^{k_1}\cdot 5^{k_2}\cdot \dots$ does the job.
  • In the case, where $m$ is even, but not a power of $2$, assume to the contrary, there are numbers not representable in that way. Then, by the well-ordering principle, there is a smallest one, which we denote by $n$. As $n$ is even, there is a $m\in\mathbb N$ with $2m=n$. Since $m<n$, $m$ has a representation $m=2^pk$, but then $n=2^{p+1}k$, a contradiction.
Related Question