Suppose that $d$ divides $2^{r+1}$ but does not divide $2^r$ or $2$. Show that $d$ must equal $2^{r+1}$. Let $r$, $d$ be positive integers, with $d>1$. 
Suppose that $d$ divides $2^{r+1}$ but does not divide $2^r$ or $2$. Show that $d$ must equal $2^{r+1}$.
 A: By unique prime factorization, $d = 2^k$ for some $1 \leq k \leq r + 1$. If $k \leq r$, then $d$ divides $2^r$. Hence $k = r + 1$ and you have $d = 2^{r + 1}$.
A: Hint $\, $ For $\rm\,p\,$ prime, $\rm\: p^{n+1} = cd\:\Rightarrow\:\color{#0A0}{\frac{p^n}d} = \color{#C00}{\frac{c}p}\:$ so $\rm\:\color{#0A0}{d\nmid p^n}\:$ $\Rightarrow$ $\rm\:\color{#C00}{p\nmid c}\:\Rightarrow\:p^{n+1}\:|\:d\:$ $\Rightarrow$ $\rm\:c=1\ \ $ QED
Remark $\, $ It's a special case of the following widely-applicable factorization refinement Lemma.
Lemma $\rm\ \ ab = cd\:\Rightarrow\:(a,d)(b,d) = d,\ $ if  $\rm\:(\color{#C00}{a,b,c,d}) = 1\:$
 and $\rm\:a,b,c,d\in \Bbb N$  
Proof $\rm\ \ \ \ (a,d)(b,d)\, =\, (ab,d(a,b,d)) \,=\, d(\color{#C00}{c,a,b,d}) = d$
A: Think this way: if $d$ divides $2^{r+1}$ then what does $d$ look like?  Well, first take the prime factorization of $2^{r+1} = 2 \cdot 2 \cdot \ldots \cdot 2$ (where there are $r+1$ 2's in the product).  So if $d$ divides this, we know $d = 2 \cdot 2 \cdot \ldots \cdot 2$ with $k$ 2's, where $0 \leq k \leq r+1$, right?
Now you have conditions that say $d$ doesn't divide $2^r$, and $d$ would divide $2^r$ if $k$ were anything up to $r$.  (You also know $d$ doesn't divide $2$, which is a useless condition since anything dividing $2$ also divides $2^r$.)  Since $k$ must be $> r$ and $\leq r+1$, the only choice is $k=r+1$ and you're done.
