Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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

share|improve this question
1  
The $2n$ restriction seems immaterial... –  Tomas Sep 7 '13 at 10:19
    
@Tomas: My computations in case $3$ invoke the same feeling. Is it intuitively true or false? Can we prove or disprove this? –  Upvote Law Area 51 Proposal Sep 10 '13 at 2:00
    
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$. –  Tomas Sep 10 '13 at 15:28
    
@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$? –  Upvote Law Area 51 Proposal Sep 13 '13 at 3:22
    
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. –  Jean-Claude Arbaut Dec 6 '13 at 0:49

3 Answers 3

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.
share|improve this answer
    
Thank you. I've rephrased my OP. Does it help to make more certain what I'm seeking? –  Upvote Law Area 51 Proposal Sep 7 '13 at 14:22

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$.

share|improve this answer

$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.

share|improve this answer
    
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..." –  Upvote Law Area 51 Proposal Sep 10 '13 at 1:58

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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