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

  • 1
    $\begingroup$ The $2n$ restriction seems immaterial... $\endgroup$ – Tomas Sep 7 '13 at 10:19
  • $\begingroup$ @Tomas: My computations in case $3$ invoke the same feeling. Is it intuitively true or false? Can we prove or disprove this? $\endgroup$ – Greek - Area 51 Proposal Sep 10 '13 at 2:00
  • $\begingroup$ Well, let $m\leq 2n$ and assume you have found a representation $m=2^pk$. Then clearly $m\geq k$. So if $m<2n$, then the $k<2n$ and if $m=2n$, then $p>0$, so $m\geq 2k>k$, hence also $k<2n$. $\endgroup$ – Tomas Sep 10 '13 at 15:28
  • $\begingroup$ @Tomas: Thanks. $\Large{\text{3.}}$ Could you please elucidate the idea behind/the "cynosure" of all your computations? $\Large{\text{4.}}$ How and why did you deduce $p > 0$? $\endgroup$ – Greek - Area 51 Proposal Sep 13 '13 at 3:22
  • $\begingroup$ This is basically a question about integer factorization (which is unique). If in the red part k is even, then you could find a larger p in the blue part. $\endgroup$ – Jean-Claude Arbaut Dec 6 '13 at 0:49

This is easy by induction one $m$. If $m$ is even then $m/2$ can be written as $2^qk$ with $k$ odd by induction, and writing $m=2^{q+1}k$ will do. If $m$ is odd writing $m=2^0m$ will do.

Unique factorization is not needed here since proving uniqueness of the expression is not asked for. It would be easy though to show uniqueness for this case "by hand" even without using unique factorization.

The only "subtle" point (mainly because it might be overlooked) is proving that $k<2n$. The argument only gives $k\leq2n$, but the latter inequality together with $k$ odd implies $k<2n$.


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.
  • $\begingroup$ Thank you. I've rephrased my OP. Does it help to make more certain what I'm seeking? $\endgroup$ – Greek - Area 51 Proposal Sep 7 '13 at 14:22

$p$ is the greatest integer such that $2^p$ divides $m$. This means that :

  1. there exists an integer $k$ such that $m = 2^p k$

  2. for any integer $q$, if there is an integer $l$ such that $m = 2^q l$, then $p \ge q$.

Suppose the $k$ you get by 1. is even. Then $k = 2l$ for some integer $l$. Hence $m = 2^p(2l) = 2^{p+1}l$. Now apply 2. with $q = p+1$ : you get that $p \ge p+1$. This is a contradiction, so $k$ must be odd.

For example, let $m = 24$. It turns out that $24 = 2^3 * 3$, so $2^3$ divides $24$. $3$ is the greatest integer $p$ such that $2^p$ divides $m$ (you can indeed check that $16,32,64,128,\ldots$ don't divide $24$) and so we find that indeed, $3$ is odd and $24 = 2^3 * 3$ was the decomposition we wanted.

The solution gave you not an algebraic formula for $p$ (as you may have wanted), but a logical formula for $p$, which is the next best thing, as it tells you exactly which $p$ you have to take.

  • $\begingroup$ Thank you. I understand the content in your Answer, but I'm still not convinced by the solution, particularly the red part. You and I both have exemplified the solution for $m = 24$, but I don't grok why the solution holds for all $m \geq 1$. At this point, I should ask about Tomas's comment: "The $2n$ restriction seems immaterial..." $\endgroup$ – Greek - Area 51 Proposal Sep 10 '13 at 1:58

For any positive integer, $m$, there will be some non-negative integer, $r$ such that $m < 2^r$. This implies that there must be some non negative integer $k \le r$ such that $2^k \mid m$ and $2^{k+1} \nmid m$.$

For example $m = 96 \lt 128 = 2^7$ and $m = 2^5 \times 3$ where $5 \le 7$.


I personally found this problem easier to do if you consolidate case 2 and 3 into one case and then prove by contradiction:

Assume m is even and that m cannot be written in the form $2^p \bullet k$ where $p$ is a nonnegative integer and k is an odd integer with $1 \le k \le 2n$. Thus, $m \neq 2^p \bullet k$. We can rewrite $2^p \bullet k = 2(2^{p-1} \bullet k)$. (Note that because m is even $p \ge 1$ and so $p-1 \ge 0$). This implies that m is not even, which directly contradicts our assumption that m is even. Therefore, we must conclude that m can be written in the form $2^p \bullet k$ where $p$ is a nonnegative integer and k is an odd integer with $1 \le k \le 2n$.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.